<!DOCTYPE HTML>
<html lang="Chinese">


<head>
    <meta charset="utf-8">
    <meta name="keywords" content="数据结构, 博客">
    <meta name="description" content="In me the tiger sniffs the rose.">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <meta name="renderer" content="webkit|ie-stand|ie-comp">
    <meta name="mobile-web-app-capable" content="yes">
    <meta name="format-detection" content="telephone=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <!-- Global site tag (gtag.js) - Google Analytics -->


    <title>数据结构 | 凡诚</title>
    <link rel="icon" type="image/png" href="/favicon.png">

    <link rel="stylesheet" type="text/css" href="/libs/awesome/css/all.css">
    <link rel="stylesheet" type="text/css" href="/libs/materialize/materialize.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/aos/aos.css">
    <link rel="stylesheet" type="text/css" href="/libs/animate/animate.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/lightGallery/css/lightgallery.min.css">
    <link rel="stylesheet" type="text/css" href="/css/matery.css">
    <link rel="stylesheet" type="text/css" href="/css/my.css">
    <script src="https://sdk.jinrishici.com/v2/browser/jinrishici.js" charset="utf-8"></script>
    <script src="/libs/jquery/jquery.min.js"></script>

<meta name="generator" content="Hexo 5.4.2"></head>



   <style>
    body{
       background-image: url(https://cdn.jsdelivr.net/gh/Tokisaki-Galaxy/res/site/medias/background.jpg);
       background-repeat:no-repeat;
       background-size:cover;
       background-attachment:fixed;
    }
</style>



<body>
    <header class="navbar-fixed">
    <nav id="headNav" class="bg-color nav-transparent">
        <div id="navContainer" class="nav-wrapper container">
            <div class="brand-logo">
                <a href="/" class="waves-effect waves-light">
                    
                    <img src="/medias/comment_bg.png" class="logo-img" alt="LOGO">
                    
                    <span class="logo-span">凡诚</span>
                </a>
            </div>
            

<a href="#" data-target="mobile-nav" class="sidenav-trigger button-collapse"><i class="fas fa-bars"></i></a>
<ul class="right nav-menu">
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/" class="waves-effect waves-light">
      
      <i class="fas fa-home" style="zoom: 0.6;"></i>
      
      <span>主页</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/tags" class="waves-effect waves-light">
      
      <i class="fas fa-tags" style="zoom: 0.6;"></i>
      
      <span>文章</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/categories" class="waves-effect waves-light">
      
      <i class="fas fa-bookmark" style="zoom: 0.6;"></i>
      
      <span>分类</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/archives" class="waves-effect waves-light">
      
      <i class="fas fa-archive" style="zoom: 0.6;"></i>
      
      <span>归档</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="" class="waves-effect waves-light">

      
      <i class="fas fa-user-circle" style="zoom: 0.6;"></i>
      
      <span>关于我</span>
      <i class="fas fa-chevron-down" aria-hidden="true" style="zoom: 0.6;"></i>
    </a>
    <ul class="sub-nav menus_item_child ">
      
      <li>
        <a href="/about">
          
          <i class="fas fa-user-circle" style="margin-top: -20px; zoom: 0.6;"></i>
          
          <span>我的信息</span>
        </a>
      </li>
      
      <li>
        <a href="/contact">
          
          <i class="fas fa-comments" style="margin-top: -20px; zoom: 0.6;"></i>
          
          <span>留言板</span>
        </a>
      </li>
      
      <li>
        <a href="/friends">
          
          <i class="fas fa-address-book" style="margin-top: -20px; zoom: 0.6;"></i>
          
          <span>友链</span>
        </a>
      </li>
      
    </ul>
    
  </li>
  
  <li>
    <a href="#searchModal" class="modal-trigger waves-effect waves-light">
      <i id="searchIcon" class="fas fa-search" title="Search" style="zoom: 0.85;"></i>
    </a>
  </li>
</ul>


<div id="mobile-nav" class="side-nav sidenav">

    <div class="mobile-head bg-color">
        
        <img src="/medias/comment_bg.png" class="logo-img circle responsive-img">
        
        <div class="logo-name">凡诚</div>
        <div class="logo-desc">
            
            In me the tiger sniffs the rose.
            
        </div>
    </div>

    

    <ul class="menu-list mobile-menu-list">
        
        <li class="m-nav-item">
	  
		<a href="/" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-home"></i>
			
			主页
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/tags" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-tags"></i>
			
			文章
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/categories" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-bookmark"></i>
			
			分类
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/archives" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-archive"></i>
			
			归档
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="javascript:;">
			
				<i class="fa-fw fas fa-user-circle"></i>
			
			关于我
			<span class="m-icon"><i class="fas fa-chevron-right"></i></span>
		</a>
            <ul  style="background:  ;" >
              
                <li>

                  <a href="/about " style="margin-left:75px">
				  
				   <i class="fa fas fa-user-circle" style="position: absolute;left:50px" ></i>
			      
		          <span>我的信息</span>
                  </a>
                </li>
              
                <li>

                  <a href="/contact " style="margin-left:75px">
				  
				   <i class="fa fas fa-comments" style="position: absolute;left:50px" ></i>
			      
		          <span>留言板</span>
                  </a>
                </li>
              
                <li>

                  <a href="/friends " style="margin-left:75px">
				  
				   <i class="fa fas fa-address-book" style="position: absolute;left:50px" ></i>
			      
		          <span>友链</span>
                  </a>
                </li>
              
            </ul>
          
        </li>
        
        
    </ul>
</div>


        </div>

        
    </nav>

</header>

    



<div class="bg-cover pd-header post-cover" style="background-image: url('/medias/featureimages/9.jpg')">
    <div class="container" style="right: 0px;left: 0px;">
        <div class="row">
            <div class="col s12 m12 l12">
                <div class="brand">
                    <h1 class="description center-align post-title">数据结构</h1>
                </div>
            </div>
        </div>
    </div>
</div>




<main class="post-container content">

    
    <link rel="stylesheet" href="/libs/tocbot/tocbot.css">
<style>
    #articleContent h1::before,
    #articleContent h2::before,
    #articleContent h3::before,
    #articleContent h4::before,
    #articleContent h5::before,
    #articleContent h6::before {
        display: block;
        content: " ";
        height: 100px;
        margin-top: -100px;
        visibility: hidden;
    }

    #articleContent :focus {
        outline: none;
    }

    .toc-fixed {
        position: fixed;
        top: 64px;
    }

    .toc-widget {
        width: 345px;
        padding-left: 20px;
    }

    .toc-widget .toc-title {
        padding: 35px 0 15px 17px;
        font-size: 1.5rem;
        font-weight: bold;
        line-height: 1.5rem;
    }

    .toc-widget ol {
        padding: 0;
        list-style: none;
    }

    #toc-content {
        padding-bottom: 30px;
        overflow: auto;
    }

    #toc-content ol {
        padding-left: 10px;
    }

    #toc-content ol li {
        padding-left: 10px;
    }

    #toc-content .toc-link:hover {
        color: #42b983;
        font-weight: 700;
        text-decoration: underline;
    }

    #toc-content .toc-link::before {
        background-color: transparent;
        max-height: 25px;

        position: absolute;
        right: 23.5vw;
        display: block;
    }

    #toc-content .is-active-link {
        color: #42b983;
    }

    #floating-toc-btn {
        position: fixed;
        right: 15px;
        bottom: 76px;
        padding-top: 15px;
        margin-bottom: 0;
        z-index: 998;
    }

    #floating-toc-btn .btn-floating {
        width: 48px;
        height: 48px;
    }

    #floating-toc-btn .btn-floating i {
        line-height: 48px;
        font-size: 1.4rem;
    }
</style>
<div class="row">
    <div id="main-content" class="col s12 m12 l9">
        <!-- 文章内容详情 -->
<div id="artDetail">
    <div class="card">
        <div class="card-content article-info">
            <div class="row tag-cate">
                <div class="col s7">
                    
                    <div class="article-tag">
                        
                            <a href="/tags/java/">
                                <span class="chip bg-color">java</span>
                            </a>
                        
                            <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">
                                <span class="chip bg-color">数据结构</span>
                            </a>
                        
                    </div>
                    
                </div>
                <div class="col s5 right-align">
                    
                    <div class="post-cate">
                        <i class="fas fa-bookmark fa-fw icon-category"></i>
                        
                            <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" class="post-category">
                                数据结构
                            </a>
                        
                    </div>
                    
                </div>
            </div>

            <div class="post-info">
                
                <div class="post-date info-break-policy">
                    <i class="far fa-calendar-minus fa-fw"></i>Publish Date:&nbsp;&nbsp;
                    2021-11-08
                </div>
                

                
                <div class="post-date info-break-policy">
                    <i class="far fa-calendar-check fa-fw"></i>Update Date:&nbsp;&nbsp;
                    2022-11-10
                </div>
                

                
                <div class="info-break-policy">
                    <i class="far fa-file-word fa-fw"></i>Word Count:&nbsp;&nbsp;
                    12.9k
                </div>
                

                
                <div class="info-break-policy">
                    <i class="far fa-clock fa-fw"></i>Read Times:&nbsp;&nbsp;
                    53 Min
                </div>
                

                
                    <div id="busuanzi_container_page_pv" class="info-break-policy">
                        <i class="far fa-eye fa-fw"></i>Read Count:&nbsp;&nbsp;
                        <span id="busuanzi_value_page_pv"></span>
                    </div>
				
            </div>
        </div>
        <hr class="clearfix">

        
        <!-- 是否加载使用自带的 prismjs. -->
        <link rel="stylesheet" href="/libs/prism/prism.css">
        

        

        <div class="card-content article-card-content">
            <div id="articleContent">
                <h1 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h1><h2 id="时间复杂度"><a href="#时间复杂度" class="headerlink" title="时间复杂度"></a>时间复杂度</h2><p>  通过函数趋势可以得到规律：</p>
<p>  **1.**算法函数中的常数可以忽略；</p>
<p>  <strong>2.算法函数中最高次幂的常数因子可以忽略；</strong> </p>
<p>  <strong>3.算法函数中最高次幂越小，算法效率越高。</strong> </p>
<p>  ==引申出时间复杂度的规律==：</p>
<p>  1.用常数1取代运行时间中的所有加法常数；</p>
<p>  2.在修改后的运行次数中，只保留高阶项；</p>
<p>  3.如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数；</p>
<h3 id="大O阶"><a href="#大O阶" class="headerlink" title="大O阶"></a>大O阶</h3><p>  在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随着n的变化情况并确定T(n)的 </p>
<p>  量级。算法的时间复杂度，就是算法的时间量度，记作:T(n)=O(f(n))。它表示随着问题规模n的增大，算法执行时间 </p>
<p>  的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度，其中f(n)是问题规模n的某个函数。 </p>
<p>  在这里，我们需要明确一个事情：执行次数=执行时间</p>
<p>  用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。一般情况下，随着输入规模n的增大，T(n)增长最 </p>
<p>  慢的算法为最优算法。 </p>
<h3 id="常见的大O阶"><a href="#常见的大O阶" class="headerlink" title="常见的大O阶"></a>常见的大O阶</h3><h4 id="1-常数阶"><a href="#1-常数阶" class="headerlink" title="1.常数阶"></a>1.常数阶</h4><p>  不含有循环，之线性执行 语句，对应计算次数不会增长：</p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arge<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
    i <span class="token operator">+=</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span></span></code></pre>

<p>上面这段代码，它的循环的时间复杂度为O(1),因为循环体中的代码需要执行1次 </p>
<h4 id="2-线性阶"><a href="#2-线性阶" class="headerlink" title="2.线性阶"></a>2.线性阶</h4><p>   一般含有非嵌套循环涉及线性阶，线性阶就是随着输入规模的扩大，对应计算次数呈直线增长，例如： </p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> 
    <span class="token keyword">int</span> sum <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> 
    <span class="token keyword">int</span> n<span class="token operator">=</span><span class="token number">100</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> 
        sum <span class="token operator">+=</span> i<span class="token punctuation">;</span> 
    <span class="token punctuation">&#125;</span>
    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"sum="</span> <span class="token operator">+</span> sum<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>上面这段代码，它的循环的时间复杂度为O(n),因为循环体中的代码需要执行n次 </p>
<h4 id="3-平方阶"><a href="#3-平方阶" class="headerlink" title="3.平方阶"></a>3.平方阶</h4><p>  一般嵌套循环属于这种时间复杂度 </p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> 
    <span class="token keyword">int</span> sum <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> 
    <span class="token keyword">int</span> n<span class="token operator">=</span><span class="token number">100</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> 
         <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;=</span> i<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> 
        	sum <span class="token operator">+=</span> i<span class="token punctuation">;</span> 
    	<span class="token punctuation">&#125;</span> 
    <span class="token punctuation">&#125;</span>
    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"sum="</span> <span class="token operator">+</span> sum<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>上面这段代码，n=100，也就是说，外层循环每执行一次，内层循环就执行100次，那总共程序想要从这两个循环 中出来，就需要执行100*100次，也就是n的平方次，所以这段代码的时间复杂度是O(n^2). </p>
<h4 id="4-立方阶"><a href="#4-立方阶" class="headerlink" title="4.立方阶"></a>4.立方阶</h4><p>  一般三层嵌套循环属于这种时间复杂度</p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> 
    <span class="token keyword">int</span> x<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>n<span class="token operator">=</span><span class="token number">100</span><span class="token punctuation">;</span> 
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span>n <span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> 
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> i<span class="token punctuation">;</span> j <span class="token operator">&lt;=</span>n <span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> i<span class="token punctuation">;</span> j <span class="token operator">&lt;=</span>n <span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                x<span class="token operator">++</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span> 
        <span class="token punctuation">&#125;</span> 
    <span class="token punctuation">&#125;</span>
    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span> 
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>



<p>上面这段代码，n=100，也就是说，外层循环每执行一次，中间循环循环就执行100次，中间循环每执行一次，最 内层循环需要执行100次，那总共程序想要从这三个循环中出来，就需要执行100<em>100</em>100次，也就是n的立方，所 以这段代码的时间复杂度是O(n^3)</p>
<h4 id="5-对数阶"><a href="#5-对数阶" class="headerlink" title="5.对数阶"></a>5.对数阶</h4><p>  一般循环中，且控制变量为立方或者平方增长，大幅减少循环次数。</p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">,</span>n<span class="token operator">=</span><span class="token number">100</span><span class="token punctuation">;</span> <span class="token keyword">while</span><span class="token punctuation">(</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    i <span class="token operator">=</span> i<span class="token operator">*</span><span class="token number">2</span><span class="token punctuation">;</span> 
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span></span></code></pre>

<p>由于每次i*2之后，就距离n更近一步，假设有x个2相乘后大于n，则会退出循环。由于是2^x=n,得到x=log(2)n,所 以这个循环的时间复杂度为O(logn); 对于对数阶，由于随着输入规模n的增大，不管底数为多少，他们的增长趋势是一样的，所以我们会忽略底数。</p>
<p>数据结构分为线性结构和非线性结构。</p>
<h4 id="时间复杂度对比"><a href="#时间复杂度对比" class="headerlink" title="时间复杂度对比"></a>时间复杂度对比</h4><p>  他们的复杂程度从低到高依次为： </p>
<p>   O(1)&lt;O(logn)&lt;O(n)&lt;O(nlogn)&lt;O(n^2)&lt;O(n^3) </p>
<p>  从平方阶开始，随着输入规模的增大，时间成本会急剧增大，所以，我们的 </p>
<p>  算法，尽可能的追求的是O(1),O(logn),O(n),O(nlogn)这几种时间复杂度，而如果发现算法的时间复杂度为平方阶、 2立方阶或者更复杂的，那我们可以分为这种算法是不可取的，需要优化。</p>
<h4 id="线性结构："><a href="#线性结构：" class="headerlink" title="线性结构："></a>线性结构：</h4><p>  数据元素之间存在一对一的线性关系。</p>
<p>  线性结构包含顺序存储结构(地址连续)和链式存储结构(地址可以不连续)。</p>
<p>  包括：数组，队列，链表，栈。</p>
<h4 id="非线性结构"><a href="#非线性结构" class="headerlink" title="非线性结构"></a>非线性结构</h4><p>  包括：二维数组，多维数组，广义表，树结构，图结构</p>
<h2 id="稀疏数组和队列"><a href="#稀疏数组和队列" class="headerlink" title="稀疏数组和队列"></a>稀疏数组和队列</h2><h4 id="稀疏数组"><a href="#稀疏数组" class="headerlink" title="稀疏数组"></a>稀疏数组</h4><blockquote>
<p>记录数组一共有几行几列，有多少个不同的值。</p>
<p>  把具有不同值的行列及值记录在一个小规模的数组中，从而缩小程序的规模。</p>
</blockquote>
<p><img src="./img/%E7%A8%80%E7%96%8F%E6%95%B0%E7%BB%84.png"></p>
<p>二维数组转稀疏数组</p>
<ol>
<li>遍历原始的二维数组，得到有效数据的个数sum。</li>
<li>根据sum就可以创建稀疏数组sparseArr int[sum + 1][3]</li>
<li>将二维数组的有效数据存入到稀疏数组。</li>
<li>将稀疏数组存储到磁盘</li>
</ol>
<p>稀疏数组转原始的二维数组</p>
<ol>
<li>从磁盘读入稀疏数组。</li>
<li>先读取稀疏数组的第一行，根据第一行的数据，获得原始数组的行数和列数，创建原始的二维数组。</li>
<li>读取稀疏数组后几行的数据，并赋给原始的二维数组。</li>
</ol>
<p>代码实现：</p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token comment">//创建一个二维数组 11 * 11</span>
        <span class="token keyword">int</span> chessArr1<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token number">11</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">11</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        chessArr1<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
        chessArr1<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">2</span><span class="token punctuation">;</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"-----原始的数组---------"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span> <span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token number">11</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> <span class="token number">11</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">print</span><span class="token punctuation">(</span>chessArr1<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token string">"\t"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>

        <span class="token keyword">int</span> sum <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">//用于保存原始二维数组中的有效数据个数</span>

        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token operator">:</span>chessArr1<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> arri<span class="token operator">:</span>arr<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>arri <span class="token operator">!=</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                    sum<span class="token operator">++</span><span class="token punctuation">;</span>
                <span class="token punctuation">&#125;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"一共有"</span> <span class="token operator">+</span> sum <span class="token operator">+</span> <span class="token string">"个有效数据"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>



        <span class="token keyword">int</span> sparseArr<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token keyword">int</span><span class="token punctuation">[</span>sum<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        sparseArr<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">11</span><span class="token punctuation">;</span>
        sparseArr<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">11</span><span class="token punctuation">;</span>
        sparseArr<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span> <span class="token operator">=</span> sum<span class="token punctuation">;</span>

            <span class="token comment">//创建稀疏数组,实现二维数组转稀疏数组</span>
        <span class="token keyword">int</span> count <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>   <span class="token comment">//计数器</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span> <span class="token punctuation">;</span>i<span class="token operator">&lt;</span> <span class="token number">11</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> <span class="token number">11</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>chessArr1<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                    count<span class="token operator">++</span><span class="token punctuation">;</span>
                    sparseArr<span class="token punctuation">[</span>count<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> i<span class="token punctuation">;</span>
                    sparseArr<span class="token punctuation">[</span>count<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> j<span class="token punctuation">;</span>
                    sparseArr<span class="token punctuation">[</span>count<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span> <span class="token operator">=</span> chessArr1<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
                <span class="token punctuation">&#125;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>


        <span class="token comment">//遍历稀疏数组</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"-----------稀疏数组-----------"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span> <span class="token punctuation">;</span>i<span class="token operator">&lt;</span>sum <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> <span class="token number">3</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">print</span><span class="token punctuation">(</span>sparseArr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token string">"\t"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>

        <span class="token comment">//稀疏数组转二维数组</span>
        <span class="token keyword">int</span> chessArr2<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token keyword">int</span><span class="token punctuation">[</span>sparseArr<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">[</span>sparseArr<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> sparseArr<span class="token punctuation">.</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            chessArr2<span class="token punctuation">[</span>sparseArr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">[</span>sparseArr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">=</span> sparseArr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>

        <span class="token comment">//遍历新生成的数组</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"---------重新生成的数组---------------"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arri <span class="token operator">:</span>chessArr2<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> ai<span class="token operator">:</span>arri<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">print</span><span class="token punctuation">(</span>ai <span class="token operator">+</span> <span class="token string">"\t"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>

    <span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>





<h4 id="队列"><a href="#队列" class="headerlink" title="队列"></a>队列</h4><p>  队列是一个有序列表，可以使用数组或者链表来实现。</p>
<p>  遵循先入先出的原则。即：先存入队列的数据，要先取出，后存入的要后取出。</p>
<p>  队列可以使用数组实现，也可以使用链表实现。</p>
<h5 id="入队"><a href="#入队" class="headerlink" title="入队"></a>入队</h5><ol>
<li>判断尾指针rear小于队列的最大下标maxSize-1(队列未满)。</li>
<li>将rear的值加一，将数据存入rear所指的数组元素中，否则无法存入数据。    rear == maxSize - 1[队列满]</li>
</ol>
<h5 id="出队"><a href="#出队" class="headerlink" title="出队"></a>出队</h5><ol>
<li>判断rear ！= front(队列非空)。</li>
<li>将front的值加一，返回front对应数组下标的值。</li>
</ol>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">class</span> <span class="token class-name">ArrayQueue</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> maxSize<span class="token punctuation">;</span>  <span class="token comment">//队列最大值</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> front<span class="token punctuation">;</span>  <span class="token comment">//队列头</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> rear<span class="token punctuation">;</span>   <span class="token comment">//队列尾</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token punctuation">;</span>  <span class="token comment">//该数组用于存放数据</span>


    <span class="token comment">//创建队列的构造器</span>
    <span class="token keyword">public</span> <span class="token class-name">ArrayQueue</span><span class="token punctuation">(</span><span class="token keyword">int</span> maxSize<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>maxSize <span class="token operator">=</span> maxSize<span class="token punctuation">;</span>
        arr <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token keyword">int</span><span class="token punctuation">[</span>maxSize<span class="token punctuation">]</span><span class="token punctuation">;</span>
        front<span class="token operator">=</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        rear<span class="token operator">=</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//判断队列是否为满</span>
    <span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">isFull</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">return</span> rear <span class="token operator">==</span> maxSize <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//判断队列是否为空</span>
    <span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">return</span> rear <span class="token operator">==</span> front<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//添加数据到队列</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">addQueue</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token comment">//判断队列是否为满</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isFull</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"队列满，无法加入数据"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        rear<span class="token operator">++</span><span class="token punctuation">;</span>
        arr<span class="token punctuation">[</span>rear<span class="token punctuation">]</span> <span class="token operator">=</span> n<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//获取队列的数据</span>
    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">getQueue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token comment">//判断队列中是否为空</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">RuntimeException</span><span class="token punctuation">(</span><span class="token string">"队列空，不能取得数据"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        front<span class="token operator">++</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> arr<span class="token punctuation">[</span>front<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//显示队列的所有数据</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">showQueue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"队列为空，没有数据"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>i <span class="token operator">&lt;</span> arr<span class="token punctuation">.</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"arr[%d]=%d\n"</span><span class="token punctuation">,</span>i<span class="token punctuation">,</span>arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//显示队列的头部数据</span>
    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">headQueue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"队列为空，没有数据"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">RuntimeException</span><span class="token punctuation">(</span><span class="token string">"队列空，不能取得数据"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token keyword">return</span> arr<span class="token punctuation">[</span>front <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>


<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>





<h4 id="环形队列"><a href="#环形队列" class="headerlink" title="环形队列"></a>环形队列</h4><p>  数组模拟队列时，只能使用一次，不能达到复用效果。</p>
<p>环形队列思路(取模的方式实现)</p>
<ol>
<li>front 变量的含义做一个调整：front就指向队列的第一个元素，也就是arr[front]就是队列的第一个元素。front的初始值为 0；</li>
<li>rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间作为约定，rear的初始值为0；</li>
<li>当队列满时，条件为：(rear + 1)%maxSize = front;</li>
<li>当队列为空时，rear == front</li>
<li>队列中有效的数据的个数为： (rear + maxSize - front)%maxSize</li>
</ol>
<ul>
<li>front为下一次获得的位置，sear为下一次存放的位置。</li>
</ul>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">class</span> <span class="token class-name">CircleArray</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> maxSize<span class="token punctuation">;</span>  <span class="token comment">//队列最大值</span>
    <span class="token comment">//front 变量的含义做一个调整：front就指向队列的第一个元素，也就是arr[front]</span>
    <span class="token comment">// 就是队列的第一个元素。front的初始值为 0；</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> front<span class="token punctuation">;</span>
    <span class="token comment">//rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置</span>
    <span class="token comment">// 因为希望空出一个空间作为约定，rear的初始值为0；</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> rear<span class="token punctuation">;</span>   <span class="token comment">//队列尾</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token punctuation">;</span>  <span class="token comment">//该数组用于存放数据</span>


    <span class="token comment">//创建队列的构造器</span>
    <span class="token keyword">public</span> <span class="token class-name">CircleArray</span><span class="token punctuation">(</span><span class="token keyword">int</span> maxSize<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>maxSize <span class="token operator">=</span> maxSize<span class="token punctuation">;</span>
        arr <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token keyword">int</span><span class="token punctuation">[</span>maxSize<span class="token punctuation">]</span><span class="token punctuation">;</span>
        front<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
        rear<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//判断队列是否为满</span>
    <span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">isFull</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">return</span> <span class="token punctuation">(</span> rear <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">)</span><span class="token operator">%</span>maxSize <span class="token operator">==</span> front<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//判断队列是否为空</span>
    <span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">return</span> rear <span class="token operator">==</span> front<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//添加数据到队列</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">addQueue</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token comment">//判断队列是否为满</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isFull</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"队列满，无法加入数据"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token comment">//直接将数据加入</span>
        arr<span class="token punctuation">[</span>rear<span class="token punctuation">]</span> <span class="token operator">=</span> n<span class="token punctuation">;</span>
        <span class="token comment">//将rear后移，使用取模放置数组下标越界</span>
        rear <span class="token operator">=</span> <span class="token punctuation">(</span>rear <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">%</span>maxSize<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//获取队列的数据</span>
    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">getQueue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token comment">//判断队列中是否为空</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">RuntimeException</span><span class="token punctuation">(</span><span class="token string">"队列空，不能取得数据"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token comment">//这里front指向队列的第一个元素</span>
        <span class="token comment">//1.先把front对应数组中的值保存到一个临时变量</span>
        <span class="token comment">//2.将front后移</span>
        <span class="token comment">//3.将临时变量返回</span>
        <span class="token keyword">int</span> value <span class="token operator">=</span> arr<span class="token punctuation">[</span>front<span class="token punctuation">]</span><span class="token punctuation">;</span>
        front <span class="token operator">=</span> <span class="token punctuation">(</span>front <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">%</span>maxSize<span class="token punctuation">;</span>
        <span class="token keyword">return</span> value<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//显示队列的所有数据</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">showQueue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"队列为空，没有数据"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token comment">//从front开始遍历，</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> front<span class="token punctuation">;</span>i <span class="token operator">&lt;</span> <span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"arr[%d]=%d\n"</span><span class="token punctuation">,</span>i<span class="token operator">%</span>maxSize<span class="token punctuation">,</span>arr<span class="token punctuation">[</span>i<span class="token operator">%</span>maxSize<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//显示队列的头部数据</span>
    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">headQueue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"队列为空，没有数据"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">RuntimeException</span><span class="token punctuation">(</span><span class="token string">"队列空，不能取得数据"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token keyword">return</span> arr<span class="token punctuation">[</span>front<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//求出当前队列有效数据的个数</span>
    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">return</span> <span class="token punctuation">(</span>rear <span class="token operator">+</span> maxSize <span class="token operator">-</span>front<span class="token punctuation">)</span><span class="token operator">%</span>maxSize<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>



<h2 id="链表"><a href="#链表" class="headerlink" title="链表"></a>链表</h2><ol>
<li>链表是以节点的方式来存储。</li>
<li>每个节点包含data域：存储数据，next域：指向下一个节点。</li>
<li>链表的各个节点不一定是连续存储。</li>
<li>链表分为带头节点的链表和没有头节点的链表，根据实际 情况确定。</li>
</ol>
<p><img src="./img/%E9%93%BE%E8%A1%A8%E7%BB%93%E6%9E%84.png"></p>
<h4 id="单向列表"><a href="#单向列表" class="headerlink" title="单向列表"></a>单向列表</h4><h5 id="添加："><a href="#添加：" class="headerlink" title="添加："></a>添加：</h5><ol>
<li><p>先创建一个head头节点，作用就是表示单链表的头。</p>
</li>
<li><p>每次添加一个节点，就直接加入到链表的最后。</p>
</li>
</ol>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token class-name">HeroNode</span> heroNode<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token comment">//头节点不能被改变，所以使用辅助变量</span>
        <span class="token class-name">HeroNode</span> temp <span class="token operator">=</span> head<span class="token punctuation">;</span>
        <span class="token comment">//遍历链表找到最后的元素</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token boolean">true</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token comment">//循环到链表最后</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>temp<span class="token punctuation">.</span>next<span class="token operator">==</span><span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            <span class="token comment">//未循环到链表最后，将当前元素指向向后移动</span>
            temp <span class="token operator">=</span> temp<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token comment">//当退出循环时，已经找到链表的最后一个元素</span>
        temp<span class="token punctuation">.</span>next <span class="token operator">=</span> heroNode<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>



<hr>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token comment">//第二种添加方式，根据序号顺序插入</span>
  <span class="token comment">//如果相同的序号则报错</span>
  <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">addByOrder</span><span class="token punctuation">(</span><span class="token class-name">HeroNode</span> heroNode<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
      <span class="token comment">//头节点不能被改变，所以使用辅助变量</span>
      <span class="token class-name">HeroNode</span> temp <span class="token operator">=</span> head<span class="token punctuation">;</span>
      <span class="token comment">//定义标记，是否有经有重读序号</span>
      <span class="token keyword">boolean</span> flag <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
      <span class="token comment">//当遍历到最后，或遍历到的节点的下一个节点的no属性大于当前插入</span>
      <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token boolean">true</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
          <span class="token keyword">if</span><span class="token punctuation">(</span>temp<span class="token punctuation">.</span>next <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
              <span class="token keyword">break</span><span class="token punctuation">;</span>
          <span class="token punctuation">&#125;</span>
          <span class="token keyword">if</span><span class="token punctuation">(</span>temp<span class="token punctuation">.</span>next<span class="token punctuation">.</span>no   heroNode<span class="token punctuation">.</span>no<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
              <span class="token keyword">break</span><span class="token punctuation">;</span>
          <span class="token punctuation">&#125;</span><span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>temp<span class="token punctuation">.</span>next<span class="token punctuation">.</span>no <span class="token operator">==</span> heroNode<span class="token punctuation">.</span>no<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
              flag <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
              <span class="token keyword">break</span><span class="token punctuation">;</span>
          <span class="token punctuation">&#125;</span>
        temp <span class="token operator">=</span> temp<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
      <span class="token punctuation">&#125;</span>
      <span class="token comment">//当退出循环时候找到适合的位置</span>
      <span class="token comment">//判断flag的值来确定是都插入</span>
      <span class="token keyword">if</span><span class="token punctuation">(</span>flag<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">//不能添加，说明编号存在</span>
          <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"编号重复无法插入"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token punctuation">&#125;</span><span class="token keyword">else</span><span class="token punctuation">&#123;</span>
          heroNode<span class="token punctuation">.</span>next <span class="token operator">=</span> temp<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
          temp<span class="token punctuation">.</span>next <span class="token operator">=</span> heroNode<span class="token punctuation">;</span>
      <span class="token punctuation">&#125;</span>

  <span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
   <pre class="line-numbers language-java" data-language="java"><code class="language-java">

<span class="token keyword">class</span> <span class="token class-name">SingleLinkedList</span><span class="token punctuation">&#123;</span>
    <span class="token comment">//初始化头节点，头节点不存放数据</span>
    <span class="token keyword">private</span> <span class="token class-name">HeroNode</span> head <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">HeroNode</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token string">""</span><span class="token punctuation">,</span><span class="token string">""</span><span class="token punctuation">)</span><span class="token punctuation">;</span>


    <span class="token comment">//使用辅助变量，遍历当前链表</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">list</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"当前链表为空"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token comment">//头节点不能移动需要需要个辅助变量</span>


        <span class="token class-name">HeroNode</span> temp <span class="token operator">=</span> head<span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token boolean">true</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token comment">//判断是否到链表最后</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>temp<span class="token punctuation">.</span>next <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            <span class="token comment">//输出节点的信息</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token comment">//将temp后移</span>
            temp <span class="token operator">=</span> temp<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span>


<span class="token comment">//定义一个HeroNode</span>
<span class="token keyword">class</span> <span class="token class-name">HeroNode</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">public</span> <span class="token keyword">int</span> no<span class="token punctuation">;</span>
    <span class="token keyword">public</span> <span class="token class-name">String</span> name<span class="token punctuation">;</span>
    <span class="token keyword">public</span> <span class="token class-name">String</span> nickname<span class="token punctuation">;</span>
    <span class="token keyword">public</span> <span class="token class-name">HeroNode</span> next<span class="token punctuation">;</span>

    <span class="token keyword">public</span> <span class="token class-name">HeroNode</span><span class="token punctuation">(</span><span class="token keyword">int</span> no<span class="token punctuation">,</span> <span class="token class-name">String</span> name<span class="token punctuation">,</span> <span class="token class-name">String</span> nickname<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>no <span class="token operator">=</span> no<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>name <span class="token operator">=</span> name<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>nickname <span class="token operator">=</span> nickname<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token class-name">String</span> <span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">return</span> <span class="token string">"HeroNode&#123;"</span> <span class="token operator">+</span>
                <span class="token string">"no="</span> <span class="token operator">+</span> no <span class="token operator">+</span>
                <span class="token string">", name='"</span> <span class="token operator">+</span> name <span class="token operator">+</span> <span class="token char">'\''</span> <span class="token operator">+</span>
                <span class="token string">", nickname='"</span> <span class="token operator">+</span> nickname <span class="token operator">+</span> <span class="token char">'\''</span> <span class="token operator">+</span>
                <span class="token string">", next="</span> <span class="token operator">+</span> next <span class="token operator">+</span>
                <span class="token char">'&#125;'</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>



<h5 id="修改："><a href="#修改：" class="headerlink" title="修改："></a>修改：</h5><p>  修改指定的节点</p>
  <pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token comment">//修改节点的信息，根据no编号来修改，即no编号不能改</span>
<span class="token comment">//说明</span>
<span class="token comment">/*
1. 根据no来修改
 */</span>
<span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">update</span><span class="token punctuation">(</span><span class="token class-name">HeroNode</span> heroNode<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"链表为空"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
 
    <span class="token comment">//定义辅助变量</span>
    <span class="token class-name">HeroNode</span> temp <span class="token operator">=</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    <span class="token keyword">boolean</span> flag <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>  <span class="token comment">//表示是否找到该节点</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token boolean">true</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>temp <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>   <span class="token comment">//已经遍历完成列表</span>
        <span class="token punctuation">&#125;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>temp<span class="token punctuation">.</span>no <span class="token operator">==</span> heroNode<span class="token punctuation">.</span>no<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token comment">//找到对应编号的no</span>
            flag <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        temp <span class="token operator">=</span> temp<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token comment">//根据flag判断是否找到要修改的节点</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>flag<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        temp<span class="token punctuation">.</span>name <span class="token operator">=</span> heroNode<span class="token punctuation">.</span>name<span class="token punctuation">;</span>
        temp<span class="token punctuation">.</span>nickname <span class="token operator">=</span> heroNode<span class="token punctuation">.</span>nickname<span class="token punctuation">;</span>
 
    <span class="token punctuation">&#125;</span><span class="token keyword">else</span><span class="token punctuation">&#123;</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"没有找到编号为%d的节点"</span><span class="token punctuation">,</span>heroNode<span class="token punctuation">.</span>no<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
 
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h5 id="删除："><a href="#删除：" class="headerlink" title="删除："></a>删除：</h5><ol>
<li>找到需要删除节点的前一个节点</li>
<li>temp.next == temp.next.next;</li>
<li>被删除的节点将不会有其他引用指向，将被垃圾回收机制回收。</li>
</ol>
<pre class="line-numbers language-java" data-language="java"><code class="language-java">    <span class="token comment">/*
    1. 找到需要删除节点的前一个节点
    2. temp.next == temp.next.next;
    3. 被删除的节点将不会有其他引用指向，将背垃圾回收机制回收。
*/</span>

    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">delete</span><span class="token punctuation">(</span><span class="token keyword">int</span> no<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token class-name">HeroNode</span> temp <span class="token operator">=</span> head<span class="token punctuation">;</span>
        <span class="token comment">//标志是否周到待删除的节点</span>
        <span class="token keyword">boolean</span> flag <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token boolean">true</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>temp<span class="token punctuation">.</span>next <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>temp<span class="token punctuation">.</span>next<span class="token punctuation">.</span>no <span class="token operator">==</span> no<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                flag <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            temp <span class="token operator">=</span> temp<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>flag <span class="token operator">==</span> <span class="token boolean">true</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            temp<span class="token punctuation">.</span>next <span class="token operator">=</span> temp<span class="token punctuation">.</span>next<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span><span class="token keyword">else</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"没有找到编号为%d的节点"</span><span class="token punctuation">,</span>no<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>





<h5 id="反转链表"><a href="#反转链表" class="headerlink" title="反转链表"></a>反转链表</h5><p>  定义一个reverseHead = head；</p>
<p>  从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead.next的位置上，使新取出节点的next指向原本的reverseHead.next。</p>
<p>  原来链表的head.next = reverseHead.next</p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token comment">/*
   定义一个reverseHead = head；

   从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead.next的位置上，使新取出节点的next指向原本的reverseHead.next。

   原来链表的head.next = reverseHead.next

    */</span>

   <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">reverseList</span><span class="token punctuation">(</span><span class="token class-name">HeroNode</span> head<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
       <span class="token comment">//如果当前链表为空，或者只有一个节点，无需反转，直接返回</span>
       <span class="token keyword">if</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next <span class="token operator">==</span> <span class="token keyword">null</span><span class="token operator">||</span>head<span class="token punctuation">.</span>next<span class="token punctuation">.</span>next<span class="token operator">==</span><span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
           <span class="token comment">//只有一个节点无需反转</span>
           <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"节点数有限无需反转"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
           <span class="token keyword">return</span><span class="token punctuation">;</span>
       <span class="token punctuation">&#125;</span>
       <span class="token comment">//定义辅助变量。指向当前节点和下一个节点</span>
       <span class="token class-name">HeroNode</span> cur <span class="token operator">=</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
       <span class="token class-name">HeroNode</span> next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
       <span class="token class-name">HeroNode</span> reverseHead <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">HeroNode</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token string">""</span><span class="token punctuation">,</span><span class="token string">""</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
       <span class="token keyword">while</span> <span class="token punctuation">(</span>cur <span class="token operator">!=</span><span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
           next <span class="token operator">=</span> cur<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
           cur<span class="token punctuation">.</span>next <span class="token operator">=</span> reverseHead<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
           reverseHead<span class="token punctuation">.</span>next <span class="token operator">=</span> cur<span class="token punctuation">;</span>
           cur <span class="token operator">=</span> next<span class="token punctuation">;</span>
       <span class="token punctuation">&#125;</span>
       <span class="token comment">//将head替换反转后的头</span>
       head<span class="token punctuation">.</span>next <span class="token operator">=</span> reverseHead<span class="token punctuation">.</span>next<span class="token punctuation">;</span>

   <span class="token punctuation">&#125;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>



<h4 id="双向链表"><a href="#双向链表" class="headerlink" title="双向链表"></a>双向链表</h4><ul>
<li>单项链表查找方向只能是一个方向。双向链表可以向前或者向后查找。</li>
<li>单向链表不能自我删除，要靠辅助节点，而双向链表可以自我删除。</li>
<li>双向链表有指向前一个节点的pre属性和指向后一个几点的next属性。</li>
</ul>
<h5 id="添加：-1"><a href="#添加：-1" class="headerlink" title="添加："></a>添加：</h5><pre class="line-numbers language-java" data-language="java"><code class="language-java"> <span class="token comment">//添加节点到双向链表</span>
    <span class="token comment">//当不考虑排序的情况下</span>
    <span class="token comment">//1.找到当前链表的最后一个节点</span>
    <span class="token comment">//2.将最后节点的next属性指向新的节点</span>
    <span class="token comment">//3.将新的节点的pre属性指向当前链表最后一个节点</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token class-name">HeroNode2</span> heroNode<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token comment">//头节点不能被改变，所以使用辅助变量</span>
        <span class="token class-name">HeroNode2</span> temp <span class="token operator">=</span> head<span class="token punctuation">;</span>
        <span class="token comment">//遍历链表找到最后的元素</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token boolean">true</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token comment">//循环到链表最后</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>temp<span class="token punctuation">.</span>next<span class="token operator">==</span><span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            <span class="token comment">//未循环到链表最后，将当前元素指向向后移动</span>
            temp <span class="token operator">=</span> temp<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token comment">//当退出循环时，已经找到链表的最后一个元素</span>
        <span class="token comment">//双向链表互相连接</span>
        temp<span class="token punctuation">.</span>next <span class="token operator">=</span> heroNode<span class="token punctuation">;</span>
        heroNode<span class="token punctuation">.</span>pre <span class="token operator">=</span> temp<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
<span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span>
   <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">addByOrder</span><span class="token punctuation">(</span><span class="token class-name">HeroNode2</span> heroNode<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token comment">//头节点不能被改变，所以使用辅助变量</span>
        <span class="token class-name">HeroNode2</span> temp <span class="token operator">=</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>

        <span class="token comment">//定义标记，是否有经有重读序号</span>
        <span class="token keyword">boolean</span> flag <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
        <span class="token comment">//当遍历到最后，或遍历到的节点的下一个节点的no属性大于当前插入</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token boolean">true</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>temp <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>temp<span class="token punctuation">.</span>no   heroNode<span class="token punctuation">.</span>no<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span><span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>temp<span class="token punctuation">.</span>no <span class="token operator">==</span> heroNode<span class="token punctuation">.</span>no<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                flag <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            temp <span class="token operator">=</span> temp<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token comment">//当退出循环时候找到适合的位置</span>
        <span class="token comment">//判断flag的值来确定是都插入</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>flag<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">//不能添加，说明编号存在</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"编号重复无法插入"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span><span class="token keyword">else</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>temp <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                temp<span class="token punctuation">.</span>pre<span class="token punctuation">.</span>next <span class="token operator">=</span> heroNode<span class="token punctuation">;</span>
                heroNode<span class="token punctuation">.</span>pre <span class="token operator">=</span> temp<span class="token punctuation">.</span>pre<span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>   <span class="token keyword">else</span><span class="token punctuation">&#123;</span>
                temp<span class="token punctuation">.</span>pre<span class="token punctuation">.</span>next <span class="token operator">=</span> heroNode<span class="token punctuation">;</span>
                heroNode<span class="token punctuation">.</span>pre <span class="token operator">=</span> temp<span class="token punctuation">.</span>pre<span class="token punctuation">;</span>
                temp<span class="token punctuation">.</span>pre <span class="token operator">=</span> heroNode<span class="token punctuation">;</span>
                heroNode<span class="token punctuation">.</span>next <span class="token operator">=</span> temp<span class="token punctuation">;</span>

            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>

    <span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>



<h5 id="修改"><a href="#修改" class="headerlink" title="修改"></a>修改</h5><pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token comment">//修改节点的信息，根据no编号来修改，即no编号不能改</span>
    <span class="token comment">//说明</span>
    <span class="token comment">/*
    1. 根据no来修改
     */</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">update</span><span class="token punctuation">(</span><span class="token class-name">HeroNode2</span> heroNode<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"链表为空"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>

        <span class="token comment">//定义辅助变量</span>
        <span class="token class-name">HeroNode2</span> temp <span class="token operator">=</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token keyword">boolean</span> flag <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>  <span class="token comment">//表示石佛找到该节点</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token boolean">true</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>temp <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>   <span class="token comment">//已经遍历完成列表</span>
            <span class="token punctuation">&#125;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>temp<span class="token punctuation">.</span>no <span class="token operator">==</span> heroNode<span class="token punctuation">.</span>no<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token comment">//找到对应编号的no</span>
                flag <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            temp <span class="token operator">=</span> temp<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token comment">//根据flag判断是否找到要修改的节点</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>flag<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            temp<span class="token punctuation">.</span>name <span class="token operator">=</span> heroNode<span class="token punctuation">.</span>name<span class="token punctuation">;</span>
            temp<span class="token punctuation">.</span>nickname <span class="token operator">=</span> heroNode<span class="token punctuation">.</span>nickname<span class="token punctuation">;</span>

        <span class="token punctuation">&#125;</span><span class="token keyword">else</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"没有找到编号为%d的节点"</span><span class="token punctuation">,</span>heroNode<span class="token punctuation">.</span>no<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>

    <span class="token punctuation">&#125;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>





<h5 id="删除"><a href="#删除" class="headerlink" title="删除"></a>删除</h5><p>  自我删除：</p>
<p>  temp.pre.next = temp.next;</p>
<p>  temp.next.pre = temp.pre;   //如果删除最后一个节点会空指针异常</p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token comment">/*
    1. 双向链表找到被删除的节点自我删除
    2. temp.next == temp.next.next;
    3. 被删除的节点将不会有其他引用指向，将背垃圾回收机制回收。
*/</span>

    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">delete</span><span class="token punctuation">(</span><span class="token keyword">int</span> no<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"链表为空无法删除"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token class-name">HeroNode2</span> temp <span class="token operator">=</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token comment">//标志是否周到待删除的节点</span>
        <span class="token keyword">boolean</span> flag <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token boolean">true</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>temp <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>temp<span class="token punctuation">.</span>no <span class="token operator">==</span> no<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                flag <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            temp <span class="token operator">=</span> temp<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>flag <span class="token operator">==</span> <span class="token boolean">true</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            temp<span class="token punctuation">.</span>pre<span class="token punctuation">.</span>next <span class="token operator">=</span> temp<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>temp<span class="token punctuation">.</span>next <span class="token operator">!=</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                temp<span class="token punctuation">.</span>next<span class="token punctuation">.</span>pre <span class="token operator">=</span> temp<span class="token punctuation">.</span>pre<span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>temp<span class="token punctuation">.</span>next<span class="token punctuation">.</span>pre <span class="token operator">=</span> temp<span class="token punctuation">.</span>pre<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span><span class="token keyword">else</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"没有找到编号为%d的节点"</span><span class="token punctuation">,</span>no<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>







<h4 id="环形单向链表"><a href="#环形单向链表" class="headerlink" title="环形单向链表"></a>环形单向链表</h4><h5 id="创建："><a href="#创建：" class="headerlink" title="创建："></a>创建：</h5><ol>
<li>先创建第一个节点，让frist指向该节点，并形成环形。</li>
<li>后面当我们没创建一个新的节点，就把该节点加入到环形链表中。</li>
</ol>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token comment">//创建环形单项链表</span>
<span class="token keyword">class</span> <span class="token class-name">CircleSingleLinkedList</span><span class="token punctuation">&#123;</span>
    <span class="token comment">//初始化第一个节点</span>
    <span class="token keyword">private</span> <span class="token class-name">Boy</span> first <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
    <span class="token comment">//添加boy节点</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">addBoy</span><span class="token punctuation">(</span><span class="token keyword">int</span> nums<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token comment">//如果传入的数值小于1不是有效数值</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>nums <span class="token operator">&lt;</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"数值无效"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token class-name">Boy</span> curBoy <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>i <span class="token operator">&lt;=</span> nums<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">Boy</span> boy <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Boy</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>

            <span class="token comment">//如果时第一个节点</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>i <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                first <span class="token operator">=</span> boy<span class="token punctuation">;</span>
                first<span class="token punctuation">.</span><span class="token function">setNext</span><span class="token punctuation">(</span>first<span class="token punctuation">)</span><span class="token punctuation">;</span>
                curBoy <span class="token operator">=</span> first<span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span><span class="token keyword">else</span><span class="token punctuation">&#123;</span>
                curBoy<span class="token punctuation">.</span><span class="token function">setNext</span><span class="token punctuation">(</span>boy<span class="token punctuation">)</span><span class="token punctuation">;</span>
                boy<span class="token punctuation">.</span><span class="token function">setNext</span><span class="token punctuation">(</span>first<span class="token punctuation">)</span><span class="token punctuation">;</span>
                curBoy <span class="token operator">=</span> boy<span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>



<h5 id="遍历："><a href="#遍历：" class="headerlink" title="遍历："></a>遍历：</h5><ol>
<li>先让一个辅助指针指向frist节点。</li>
<li>然后通过一个while循环遍历该环形链表即curBoy.next == first结束。</li>
</ol>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token comment">//遍历环形指针</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">showBoy</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token comment">//判断链表是否为空</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>first <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"链表为空"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token comment">//因为first不能懂，因此我们仍然使用一个辅助指针完成遍历</span>
        <span class="token class-name">Boy</span> curBoy <span class="token operator">=</span> first<span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token boolean">true</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"编号为%d\n"</span><span class="token punctuation">,</span> curBoy<span class="token punctuation">.</span><span class="token function">getNo</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>curBoy<span class="token punctuation">.</span><span class="token function">getNext</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> first<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            curBoy <span class="token operator">=</span> curBoy<span class="token punctuation">.</span><span class="token function">getNext</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>



<p><img src="./img/%E7%BA%A6%E7%91%9F%E5%A4%AB%E9%97%AE%E9%A2%98.png"></p>
<h2 id="栈-stack"><a href="#栈-stack" class="headerlink" title="栈(stack)"></a>栈(stack)</h2><blockquote>
<p>栈是一个先入后出的有序列表</p>
</blockquote>
<blockquote>
<p>栈是限制性表中的插入和删除只能在线性表中的同一端进行的特殊的线性表，允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底。</p>
</blockquote>
<blockquote>
<p>根据栈的定义可以知道，最先放入栈中的元素在栈底，最后放入栈的元素在栈顶，而删除元素正好相反，最先放入的最后删除，最后放入的最先删除。</p>
</blockquote>
<h3 id="数组栈"><a href="#数组栈" class="headerlink" title="数组栈"></a>数组栈</h3><p>  使用数组模拟栈</p>
<p>  定义一个top变量来表示栈顶，初始化为-1</p>
<p>  入栈的操作,当有数据加入到栈时：top++；stack[top] = data</p>
<p>  出栈的操作，int value = stack[top];top–;return value;</p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">class</span> <span class="token class-name">ArrayStack</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> maxSize<span class="token punctuation">;</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> stack<span class="token punctuation">;</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> top <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>

    <span class="token comment">//构造器，设置栈的大小</span>
    <span class="token keyword">public</span> <span class="token class-name">ArrayStack</span><span class="token punctuation">(</span><span class="token keyword">int</span> maxSize<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>maxSize <span class="token operator">=</span> maxSize<span class="token punctuation">;</span>
        stack <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token keyword">int</span><span class="token punctuation">[</span>maxSize<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//栈满</span>
    <span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">isFill</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">return</span> top <span class="token operator">==</span> maxSize <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//栈空</span>
    <span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">return</span> top <span class="token operator">==</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//入栈</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">push</span><span class="token punctuation">(</span><span class="token keyword">int</span> value<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token comment">//判断栈是否已经满</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isFill</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"栈已经满无法入栈"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        top<span class="token operator">++</span><span class="token punctuation">;</span>
        stack<span class="token punctuation">[</span>top<span class="token punctuation">]</span> <span class="token operator">=</span> value<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//出栈</span>
    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token comment">//判断栈是否为空</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">RuntimeException</span><span class="token punctuation">(</span><span class="token string">"栈为空无法弹出元素"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token keyword">int</span> value <span class="token operator">=</span> stack<span class="token punctuation">[</span>top<span class="token punctuation">]</span><span class="token punctuation">;</span>
        top<span class="token operator">--</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> value<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//遍历栈</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">list</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token comment">//判断栈是否为空</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"栈中没有数据"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token comment">//需要从栈顶遍历元素</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> top<span class="token punctuation">;</span>i  <span class="token operator">=</span><span class="token number">0</span> <span class="token punctuation">;</span>i<span class="token operator">--</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"stack[%d]=%d\n"</span><span class="token punctuation">,</span>i<span class="token punctuation">,</span>stack<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>


<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>



<p>使用栈结构完成计算表达式</p>
<p>  一位数字的计算方法</p>
<ol>
<li>通过一个index值(索引)，来遍历表达式。</li>
<li>如果发现扫描的是一个数字，就直接入数栈</li>
<li>如果发现扫描的是一个符号：<ol>
<li>如果符号栈没有操作符号，就直接入栈。</li>
<li>如果符号栈中 已经有操作符，且当前扫描的操作符的优先级小于或者定于栈中的操作符，就从数栈中pop出两个数字，在符号栈中pop出一个符号，进行运算，将得到的结果放入数栈，然后将当前操作符放入到符号栈中。</li>
<li>如果符号栈中已经有操作符，且扫描到的操作符的优先级大于当前栈中的操作符，就直接放入到符号栈。</li>
<li>当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数字和符号，并且运行。</li>
<li>当最后数栈中只有一个数字时，就是表达式的结果。</li>
</ol>
</li>
</ol>
<p>中缀表达式转换为后缀表达式：</p>
<ol>
<li><p>初始化两个栈:运算符栈s1和储存中间结果的栈s2;</p>
</li>
<li><p>从左至右扫描 中缀表达式;</p>
</li>
<li><p>遇到操作数时，将其压s2;</p>
</li>
<li><p>遇到运算符时，比较其与s1栈顶运算符的优先级:</p>
<ol>
<li>如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈;</li>
<li>否则，若优先级比栈顶运算符的高，也将运算符压入s1;</li>
<li>否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较;</li>
</ol>
</li>
<li><p>遇到括号时:</p>
<ol>
<li>如果是左括号“(”，则直接压入s1</li>
<li>如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2,直到遇到左括号为止，此时将这一对括号丢弃</li>
</ol>
</li>
<li><p>重复步骤2至5，直到表达式的最右边</p>
</li>
<li><p>将s1中剩余的运算符依次弹出并压入s2</p>
</li>
<li><p>依次弹出s2中的元素并输出，结果的逆向为中缀表达式对应的后缀表达式</p>
</li>
</ol>
<h2 id="递归"><a href="#递归" class="headerlink" title="递归"></a>递归</h2><blockquote>
<p>递归就是方法自己调用自己，每次调用时传入不同的变量，递归有助于解决复杂问题。 </p>
</blockquote>
<p>  递归执行规则：</p>
<ol>
<li>执行一个方法时，就创建一个新的受保护的独立的空间(栈空间)</li>
<li>方法的局部变量是独立的，不会互相影响。(如果时引用类型会相互影响)</li>
<li>递归必须向退出递归的条件逼近，否则就是无限递归。</li>
<li>当一个方法执行完毕，或者遇到return，就会返回，遵循谁调用，就将结果返回谁，同时当方法执行完毕或者返回时，该方法就执行完毕。</li>
</ol>
<h2 id="排序算法"><a href="#排序算法" class="headerlink" title="排序算法"></a>排序算法</h2><p>  内部排序：</p>
<p>  ​    指将需要处理的数据都加载到内部存储器中进行排序。</p>
<p>  外部排序：</p>
<p>  ​    数据量过大，无法全部加载到内存中，需要借助内部存储进行排序。</p>
<p>选择排序：</p>
<ul>
<li>简单选择排序</li>
<li>堆排序</li>
</ul>
<p>插入排序：</p>
<ul>
<li>直接插入排序</li>
<li>希尔排序</li>
</ul>
<p>交换排序：</p>
<ul>
<li>冒泡排序</li>
<li>快速排序</li>
</ul>
<p>归并排序：</p>
<p>基数排序：</p>
<p>  度量一个程序(算法)的执行事件的两种方法：</p>
<ol>
<li>事后统计法</li>
<li>事前估算法</li>
</ol>
<p>  时间频度：一个算法中的语句执行次数称为语句频度或者时间频度。</p>
<p>  计算时间复杂度时，可以忽略常数项和低次项，高次项的系数可以忽略。</p>
<p>创建时间复杂度：</p>
<p><img src="./img/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6.png"></p>
<p>  平均时间复杂度和最坏时间复杂度</p>
<ol>
<li>平均时间复杂度是指所有可能输入实例均以等概率出现的情况下，该算法的时间复杂度。</li>
<li>最坏情况下的时间复杂度在任何实例上运行时间的界限，保证了运行时间不会比最坏的情况下更长。</li>
<li>平均时间复杂度和最坏时间复杂度是否一致，与算法有关。</li>
</ol>
<p><img src="./img/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%9A%84%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6.png"></p>
<p>相关术语：</p>
<ul>
<li>稳定：如果a原本在b之前且a==b，排序之后a还在b之前被称作稳定。</li>
<li>内排序：所有排序都在内存中完成。</li>
<li>外排序：因为数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。</li>
<li>时间复杂度：一个算法执行所耗费的时间。</li>
<li>空间复杂度：一个算法所需要的内存的大小。</li>
</ul>
<p><img src="./img/%E5%B8%B8%E7%94%A8%E7%AE%97%E6%B3%95%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6.png"></p>
<h3 id="冒泡排序"><a href="#冒泡排序" class="headerlink" title="冒泡排序"></a>冒泡排序</h3><p>  基本思想：通过对排序序列从前向后(从下标较小的元素开始)，一次比较相邻元素的值，若发现逆序就交换次序，使值较大的元素逐渐从前移向后部。</p>
<ul>
<li>一共进行数组大小-1次大的循环</li>
<li>每个循环后交换到最大(最小)值放置到最后位置</li>
<li>每一次排序的次数再逐渐减少。</li>
<li>如果发现在某次排序中，没有发生交换，可以提前结束冒泡排序。</li>
<li><h6 id="时间复杂度为-平方阶"><a href="#时间复杂度为-平方阶" class="headerlink" title="时间复杂度为 平方阶"></a>时间复杂度为 平方阶</h6></li>
</ul>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span>未优化的冒泡排序<span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span> 
<span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> arr<span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">&#123;</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">10</span><span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">&#125;</span><span class="token punctuation">;</span>
        <span class="token comment">//定义用于交换的临时变量</span>
        <span class="token keyword">int</span> temp <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>

        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> arr<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>j <span class="token operator">&lt;</span> arr<span class="token punctuation">.</span>length<span class="token operator">-</span>i<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token comment">//如果前面的数字比后面的大，就交换</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span>   arr<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                    temp <span class="token operator">=</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
                    arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> arr<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
                    arr<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> temp<span class="token punctuation">;</span>
                <span class="token punctuation">&#125;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
<span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span>优化后的冒泡排序<span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span>
    <span class="token comment">//优化后的冒泡排序只要其中小循环没有发生交换，说明所有元素顺序已经排序完成，可以跳出循环，完成排序</span>
      <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>

        <span class="token keyword">int</span> arr<span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">&#123;</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">10</span><span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">&#125;</span><span class="token punctuation">;</span>
        <span class="token comment">//定义用于交换的临时变量</span>
        <span class="token keyword">int</span> temp <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token comment">//定义标识变量，标识是否进行了交换</span>
        <span class="token keyword">boolean</span> flag <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>

        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> arr<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>j <span class="token operator">&lt;</span> arr<span class="token punctuation">.</span>length<span class="token operator">-</span>i<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token comment">//如果前面的数字比后面的大，就交换</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span>   arr<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                    flag <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
                    temp <span class="token operator">=</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
                    arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> arr<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
                    arr<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> temp<span class="token punctuation">;</span>
                <span class="token punctuation">&#125;</span>
            <span class="token punctuation">&#125;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>flag<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span><span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
                flag <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>  <span class="token comment">//重置false，重新进行下一次的判断</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>



<h3 id="选择排序"><a href="#选择排序" class="headerlink" title="选择排序"></a>选择排序</h3><p>  选择式排序也属于内部排序法，是从排序的数据中，按照指定的规则选出来某一个元素，再依照规定交换位置达到排序的目的。</p>
<ul>
<li>选择排序一共有数组大小-1轮排序</li>
<li>每一轮排序，又是一个循环，循环的规则(代码)：<ul>
<li>先假定当前这个数是最小的数字</li>
<li>然后和后面的每个数字进行比较，如果发现有比当前数字更小的数时，就重新确定最小的数字。</li>
<li>当遍历到数组的最后时，就得到了本轮最小数字的下标。</li>
<li>将最小数字和当前轮比较的第一个数字交换位置。</li>
</ul>
</li>
</ul>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">selectSort</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>

        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>i <span class="token operator">&lt;</span> arr<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            <span class="token keyword">int</span> minIndex <span class="token operator">=</span> i<span class="token punctuation">;</span>
            <span class="token keyword">int</span> min <span class="token operator">=</span> arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> i <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> arr<span class="token punctuation">.</span>length<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span>min   arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                    min <span class="token operator">=</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>  <span class="token comment">//重置min</span>
                    minIndex <span class="token operator">=</span> j<span class="token punctuation">;</span>   <span class="token comment">//重置minIndex</span>
                <span class="token punctuation">&#125;</span>
            <span class="token punctuation">&#125;</span>
        <span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h3 id="插入排序"><a href="#插入排序" class="headerlink" title="插入排序"></a>插入排序</h3><p>  插入排序的基本思想：将n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码一次与有序元素的排序码进行比较，将 它插入到有序表中的适当位置，使之称为新的有序表。</p>
<p><img src="./img/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F.png"></p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">insertSort</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> 
        <span class="token comment">//使用插入排序法</span>

        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span> arr<span class="token punctuation">.</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token comment">//定义插入的数值</span>
            <span class="token keyword">int</span> insertVal <span class="token operator">=</span> arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token keyword">int</span> insertIndex <span class="token operator">=</span> i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span>

            <span class="token comment">//如果找到了开头或者找到比要插入值小的位置就可以选定当前为插入位置</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span>insertIndex  <span class="token operator">=</span> <span class="token number">0</span> <span class="token operator">&amp;&amp;</span> insertVal <span class="token operator">&lt;</span> arr<span class="token punctuation">[</span>insertIndex<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                arr<span class="token punctuation">[</span>insertIndex <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> arr<span class="token punctuation">[</span>insertIndex<span class="token punctuation">]</span><span class="token punctuation">;</span>
                insertIndex<span class="token operator">--</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
            <span class="token comment">//退出while循环后，当前下表为要插入的下标前一个索引</span>
            arr<span class="token punctuation">[</span>insertIndex <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> insertVal<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>



<h3 id="希尔排序"><a href="#希尔排序" class="headerlink" title="希尔排序"></a>希尔排序</h3><p>  希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。 </p>
<p>  <strong>需求：</strong> </p>
<p>  排序前：{9,1,2,5,7,4,8,6,3,5} </p>
<p>  排序后：{1,2,3,4,5,5,6,7,8,9} </p>
<p>  <strong>排序原理：</strong> </p>
<p>   1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组； </p>
<p>   2.对分好组的每一组数据完成插入排序； </p>
<p>   3.减小增长量，最小减为1，重复第二步操作。</p>
<p><img src="./img/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F.png"></p>
<ul>
<li>希尔排序—内部使用交换法</li>
</ul>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">shellSort</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
       <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr <span class="token operator">=</span> <span class="token punctuation">&#123;</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">8</span><span class="token punctuation">,</span><span class="token number">19</span><span class="token punctuation">&#125;</span><span class="token punctuation">;</span>

        <span class="token comment">//定义交换变量</span>
        <span class="token keyword">int</span> temp <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> h <span class="token operator">=</span> arr<span class="token punctuation">.</span>length<span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">;</span>h <span class="token number">0</span><span class="token punctuation">;</span>h<span class="token operator">/=</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token comment">//遍历各组中的所有元素</span>
            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> h<span class="token punctuation">;</span> i <span class="token operator">&lt;</span> arr<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                <span class="token comment">//如果当前元素大于指定步长后的元素，即交换</span>
                <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> i <span class="token punctuation">;</span>j  <span class="token operator">=</span>h<span class="token punctuation">;</span>j <span class="token operator">-=</span> h<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                    <span class="token keyword">if</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">&lt;</span> arr<span class="token punctuation">[</span>j <span class="token operator">-</span> h<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                        temp <span class="token operator">=</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
                        arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> arr<span class="token punctuation">[</span>j <span class="token operator">-</span> h<span class="token punctuation">]</span><span class="token punctuation">;</span>
                        arr<span class="token punctuation">[</span>j <span class="token operator">-</span> h<span class="token punctuation">]</span> <span class="token operator">=</span> temp<span class="token punctuation">;</span>
                    <span class="token punctuation">&#125;</span>
                <span class="token punctuation">&#125;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token class-name">Arrays</span><span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span>arr<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<ul>
<li>希尔排序—内部使用移动法</li>
</ul>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">shellSort</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token comment">//定义交换变量</span>
        <span class="token keyword">int</span> temp <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> gap <span class="token operator">=</span> arr<span class="token punctuation">.</span>length<span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">;</span>gap <span class="token number">0</span><span class="token punctuation">;</span>gap<span class="token operator">/=</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token comment">//遍历各组中的所有元素，逐个对所在的组进行直接插入如排序</span>
            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> gap<span class="token punctuation">;</span> i <span class="token operator">&lt;</span> arr<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                <span class="token keyword">int</span> j <span class="token operator">=</span> i<span class="token punctuation">;</span>
                <span class="token keyword">int</span> temp <span class="token operator">=</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">&lt;</span> arr<span class="token punctuation">[</span>j <span class="token operator">-</span> gap<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                    <span class="token keyword">while</span><span class="token punctuation">(</span>j <span class="token operator">-</span> gap  <span class="token operator">=</span> <span class="token number">0</span> <span class="token operator">&amp;&amp;</span> temp <span class="token operator">&lt;</span> arr<span class="token punctuation">[</span>j <span class="token operator">-</span> gap<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                        <span class="token comment">//移动</span>
                        arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> arr<span class="token punctuation">[</span>j <span class="token operator">-</span> gap<span class="token punctuation">]</span><span class="token punctuation">;</span>
                        j <span class="token operator">-=</span> gap<span class="token punctuation">;</span>
                        <span class="token punctuation">&#125;</span>
                    <span class="token comment">//当退出while后就给temp找到插入位置</span>
                    arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> temp<span class="token punctuation">;</span>
                <span class="token punctuation">&#125;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>





<h3 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h3><p>  快速排序是对冒泡排序的一种改进。</p>
<p>  基本思想：</p>
<p>  通过一轮排序将要排序的数据分割为独立的两个部分，其中一部分的所有数据都比另一部分的所有数据小，然后再根据此方法对这两部分数据分别进行快速排序，整个过程可以递归进行，以此达到整个数据都变成有序序列。</p>
<p>  假设对以下10个数进行快速排序：</p>
<p>  6    1    2    7    9    3    4    5    10    8<br>  我们先模拟快速排序的过程：首先，在这个序列中随便找一个数作为基准数，通常为了方便，以第一个数作为基准数。</p>
<p>  6    1    2    7    9    3    4    5    10    8<br>  在初始状态下，数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置，假设这个位置是k。现在就需要寻找这个k，并且以第k位为分界点，左边的数都≤ 6，右边的数都≥ 6。那么如何找到这个位置k 呢？</p>
<p>  我们要知道，快速排序其实是冒泡排序的一种改进，冒泡排序每次对相邻的两个数进行比较，这显然是一种比较浪费时间的。</p>
<p>  而快速排序是分别从两端开始”探测”的，先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j ，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j ”。刚开始的时候让哨兵i 指向序列的最左边，指向数字6。让哨兵j 指向序列的最右边，指向数字8。</p>
<p>  6    1    2    7    9    3    4    5    10    8<br>  i                                    j<br>  首先哨兵j开始出动。==因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动==，这一点非常重要。哨兵j 一步一步地向左挪动（即j = j − 1），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i = i + 1），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。</p>
<p>  6    1    2    7    9    3    4    5    10    8<br>  ​                         i                  j<br>  现在交换哨兵$i$和哨兵$j$所指向的元素的值。交换之后的序列如下。<br>  6    1    2    5    9    3    4    7    10    8<br>  ​                         i                j<br>  到此，第一次交换结束。接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4 &lt; 6 停下来。哨兵i也继续向右挪动的，他发现了9   6 ，停下来。此时再次进行交换，交换之后的序列如下。</p>
<p>  6    1    2    5    4    3    9    7    10    8<br>  ​                                 i         j<br>  第二次交换结束。哨兵j继续向左挪动，他发现了3 &lt; 6，又停下来。哨兵i 继续向右移动，此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下。</p>
<p>  3    1    2    5    4    6    9    7    10    8<br>  ​                                        i,j<br>  到此第一轮“探测”真正结束。现在基准数6已经归位，此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j 的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。</p>
<p>  现在我们将第一轮“探测”结束后的序列，以6为分界点拆分成两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。</p>
<p>  3    1    2    5    4    6<br>  重复第一轮的过程，应该得到如下序列：</p>
<p>  2    1    3    5    4    6<br>  OK，现在3已经归位。接下来需要处理3左边的序列：</p>
<p>  2    1    3              6<br>  处理之后，2已经归位，序列“1”只有一个数，也不需要进行任何处理，因此“1”也归位。</p>
<p>  1    2    3              6<br>  对于基数右边的序列，采用和左边相同的过程；最终将会得到这样的序列，如下。</p>
<p>  1    2    3    4    5    6    7    8    9    10</p>
<p><img src="./img/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F.png"></p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span>  <span class="token function">quickSort</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token punctuation">,</span> <span class="token keyword">int</span> begin<span class="token punctuation">,</span> <span class="token keyword">int</span> end<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>begin   end<span class="token punctuation">)</span>
            <span class="token keyword">return</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> tmp <span class="token operator">=</span> arr<span class="token punctuation">[</span>begin<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> i <span class="token operator">=</span> begin<span class="token punctuation">;</span>
        <span class="token keyword">int</span> j <span class="token operator">=</span> end<span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>i <span class="token operator">!=</span> j<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span>  <span class="token operator">=</span> tmp <span class="token operator">&amp;&amp;</span> j   i<span class="token punctuation">)</span>
                j<span class="token operator">--</span><span class="token punctuation">;</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">&lt;=</span> tmp <span class="token operator">&amp;&amp;</span> j   i<span class="token punctuation">)</span>
                i<span class="token operator">++</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>j   i<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">int</span> t <span class="token operator">=</span> arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
                arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
                arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> t<span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
        arr<span class="token punctuation">[</span>begin<span class="token punctuation">]</span> <span class="token operator">=</span> arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
        arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> tmp<span class="token punctuation">;</span>
        <span class="token function">quickSort</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> begin<span class="token punctuation">,</span> i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">quickSort</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> end<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>



<h3 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h3><p>  归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略，将问题分成一些小的问题然后递归求解，治的阶段则是将分的阶段得到的答案修补到一起，即分而治之。</p>
<p>基本介绍</p>
<p>归并排序(MERGE- SORT)是利用归并的思想实现的排序方法，该算法采用经典的分治( divide-<br>and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案修补”在一起，即分而治之)。</p>
<p><img src="./img/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E5%BD%92.png"></p>
<p>基本思想</p>
<p>1.把数组从中间划分成两个子数组;<br>2.一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素<br>3.依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。</p>
<p>看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现的详细步骤</p>
<p><img src="./img/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E5%B9%B6.png"></p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">mergeSort</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token punctuation">,</span> <span class="token keyword">int</span> left<span class="token punctuation">,</span> <span class="token keyword">int</span> right<span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> temp<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
       <span class="token keyword">if</span> <span class="token punctuation">(</span>left <span class="token operator">&lt;</span> right<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
           <span class="token keyword">int</span> mid <span class="token operator">=</span> <span class="token punctuation">(</span>left <span class="token operator">+</span> right<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">;</span> <span class="token comment">//中间索引</span>
           <span class="token comment">//向左递归进行分解</span>
           <span class="token comment">//0 - mid 即是0 - 3 &#123;8,4,5,7&#125;</span>
           <span class="token function">mergeSort</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> left<span class="token punctuation">,</span> mid<span class="token punctuation">,</span> temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
           <span class="token comment">//向右递归进行分解</span>
           <span class="token comment">//mid+1 - midright 即是4 - 7  &#123;1,3,6,2&#125;</span>
           <span class="token function">mergeSort</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> right<span class="token punctuation">,</span> temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
           <span class="token comment">//进行合并</span>
           <span class="token function">merge</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> left<span class="token punctuation">,</span> mid<span class="token punctuation">,</span> right<span class="token punctuation">,</span> temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
       <span class="token punctuation">&#125;</span>
   <span class="token punctuation">&#125;</span>
   <span class="token comment">//合并的方法</span>
   <span class="token comment">/**
    *
    *  @param  arr 排序的原始数组
    *  @param left 左边有序序列的初始索引
    *  @param mid 中间索引
    *  @param right 右边索引
    *  @param temp 做中转的数组
    **/</span>
   <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">merge</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token punctuation">,</span> <span class="token keyword">int</span> left<span class="token punctuation">,</span> <span class="token keyword">int</span> mid<span class="token punctuation">,</span> <span class="token keyword">int</span> right<span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> temp<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
       <span class="token comment">//初始化i,左边有序序列的初始索引</span>
       <span class="token keyword">int</span> i <span class="token operator">=</span> left<span class="token punctuation">;</span>
       <span class="token comment">//初始化j,右边有序序列的初始索引</span>
       <span class="token comment">//为什么要mid+1?</span>
       <span class="token comment">//因为假设数组arr&#123;1,3,5,6,2,4&#125; mid=(left+right)/2 = 2</span>
       <span class="token comment">//此时左边i=left mid左边的就是 0 - mid 即是&#123;1,3,5&#125;</span>
       <span class="token comment">//此时右边就是mid+1 - right 即是&#123;6,2,4&#125;</span>
       <span class="token keyword">int</span> j <span class="token operator">=</span> mid<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>

       <span class="token keyword">int</span> t <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span><span class="token comment">//指向temp数组的当前索引</span>

       <span class="token comment">//(-)</span>
       <span class="token comment">//先把左右两边(有序)的数据按照规则填充到temp数组</span>
       <span class="token comment">//直到左右两边的有序序列，有一边处理完毕为止</span>
       <span class="token comment">//i &lt;= mid 代表左边有序序列有值</span>
       <span class="token comment">//j &lt;= right 代表右边有序序列有值</span>
       <span class="token keyword">while</span> <span class="token punctuation">(</span>i <span class="token operator">&lt;=</span> mid <span class="token operator">&amp;</span> j <span class="token operator">&lt;=</span> right<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span><span class="token comment">//继续</span>

           <span class="token comment">//如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素</span>
           <span class="token comment">//即将左边的当前元素，拷贝到temp数组</span>
           <span class="token comment">//假设数组arr&#123;1,3,5,6,2,4&#125;</span>
           <span class="token comment">//左边 0 - mid 即是&#123;1,3,5&#125;</span>
           <span class="token comment">//右边 mid+1 -right 即是&#123;6,2,4&#125;</span>
           <span class="token comment">//若arr[i]&lt;= arr[j] 即是1 &lt;= 6</span>
           <span class="token keyword">if</span> <span class="token punctuation">(</span>arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">&lt;=</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
               temp<span class="token punctuation">[</span>t<span class="token punctuation">]</span> <span class="token operator">=</span> arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span><span class="token comment">//temp[0]=arr[i];</span>
               t <span class="token operator">+=</span> <span class="token number">1</span><span class="token punctuation">;</span><span class="token comment">//指向temp数组下一位</span>
               i <span class="token operator">+=</span> <span class="token number">1</span><span class="token punctuation">;</span><span class="token comment">//指向左边下一位arr[i+1]...</span>
           <span class="token punctuation">&#125;</span><span class="token keyword">else</span><span class="token punctuation">&#123;</span>
               <span class="token comment">//反之arr[i]  = arr[j] 左边大于右边</span>
               <span class="token comment">//则进行右边赋值给temp数组</span>
               temp<span class="token punctuation">[</span>t<span class="token punctuation">]</span> <span class="token operator">=</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span><span class="token comment">//temp[0]=arr[i];</span>
               t <span class="token operator">+=</span> <span class="token number">1</span><span class="token punctuation">;</span><span class="token comment">//指向temp数组下一位</span>
               j <span class="token operator">+=</span> <span class="token number">1</span><span class="token punctuation">;</span><span class="token comment">//指向右边边下一位arr[j+1]...</span>
           <span class="token punctuation">&#125;</span>
       <span class="token punctuation">&#125;</span>

       <span class="token comment">//(二)</span>
       <span class="token comment">//把有剩余数据的一边的数据依次全部填充到temp</span>
       <span class="token comment">//左边的有序序列还有剩余的元素，就全部填充到temp</span>
       <span class="token keyword">while</span><span class="token punctuation">(</span> i <span class="token operator">&lt;=</span> mid<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
           temp<span class="token punctuation">[</span>t<span class="token punctuation">]</span> <span class="token operator">=</span> arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
           t <span class="token operator">+=</span> <span class="token number">1</span><span class="token punctuation">;</span>
           i <span class="token operator">+=</span> <span class="token number">1</span><span class="token punctuation">;</span>
       <span class="token punctuation">&#125;</span>
       <span class="token comment">//右边的有序序列还有剩余的元素，就全部填充到temp</span>
       <span class="token keyword">while</span><span class="token punctuation">(</span> j <span class="token operator">&lt;=</span> right<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
           temp<span class="token punctuation">[</span>t<span class="token punctuation">]</span> <span class="token operator">=</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
           t <span class="token operator">+=</span> <span class="token number">1</span><span class="token punctuation">;</span>
           j <span class="token operator">+=</span> <span class="token number">1</span><span class="token punctuation">;</span>
       <span class="token punctuation">&#125;</span>

       <span class="token comment">//(三)</span>
       <span class="token comment">//将temp数组的元素拷贝到arr</span>
       <span class="token comment">//为什么 t=0 ?</span>
       <span class="token comment">//因为合并的时候按图所示数组：&#123;8,4,5,7,1,3,6,2&#125;</span>
       <span class="token comment">//最先进入的是84 left=0 right = 1</span>
       <span class="token comment">//经过上面的左边与右边比较，得出temp数组：4,8</span>
       <span class="token comment">// 此时清空指向temp数组的下标指针t 重新回到0</span>
       <span class="token comment">//tempLeft = 0 进行将temp数组里的4，8 赋值给arr数组</span>
       t <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
       <span class="token keyword">int</span> tempLeft<span class="token operator">=</span> left<span class="token punctuation">;</span>
       <span class="token keyword">while</span><span class="token punctuation">(</span> tempLeft <span class="token operator">&lt;=</span> right<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
           arr<span class="token punctuation">[</span>tempLeft<span class="token punctuation">]</span><span class="token operator">=</span>temp<span class="token punctuation">[</span>t<span class="token punctuation">]</span><span class="token punctuation">;</span>
           t <span class="token operator">+=</span> <span class="token number">1</span><span class="token punctuation">;</span><span class="token comment">//赋值成功后指向temp数组的下标指针t往后移</span>
           tempLeft <span class="token operator">+=</span><span class="token number">1</span><span class="token punctuation">;</span><span class="token comment">//84 完成后到57 此时left=2 right = 3 ...</span>
       <span class="token punctuation">&#125;</span>
   <span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>





<h3 id="基数排序"><a href="#基数排序" class="headerlink" title="基数排序"></a>基数排序</h3><ul>
<li>基数排序属于分配式排序，又称为桶子法，是通过键值的各个位的值，将要排序的元素分配到某些桶中，达到排序的作用。</li>
<li>基数排序法始于稳定的排序，基数排序是效率高且稳定的排序方法。</li>
<li>基数排序是桶排序的扩展。</li>
<li>将整数按照位数切割为不同数子根据个位数分别比较。</li>
<li>基数排序是经典的使用空间交换时间的算法，会占用辅助内存</li>
<li>如果含有负数不能使用基数排序。</li>
</ul>
<p>基数排序基本思想：</p>
<ol>
<li>将所有待比较数值统一为同样的数位长度，数位较短的数前面补零，然后，从最低位开始，依次进行一次排序，这样从最低位一直到最高位排序完成后，就变成一个有序的序列。</li>
</ol>
<p><img src="./img/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F.png"></p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">radixSort</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
		
		<span class="token keyword">int</span> max<span class="token operator">=</span>arr<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">;</span><span class="token comment">//假设第一个数就是最大数</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>arr<span class="token punctuation">.</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
			<span class="token keyword">if</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span> max<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
				max<span class="token operator">=</span>arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
			<span class="token punctuation">&#125;</span>
		<span class="token punctuation">&#125;</span>
		<span class="token keyword">int</span> maxLength<span class="token operator">=</span><span class="token punctuation">(</span>max<span class="token operator">+</span><span class="token string">" "</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">length</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token comment">//第一轮（针对每个元素的个位进行排序处理）</span>
		
		<span class="token comment">//定义一个二维数组，表示10个桶，每个桶就是一维数组</span>
		<span class="token comment">//说明：</span>
		<span class="token comment">//1.二维数组包含10个一维数组</span>
		<span class="token comment">//2.为了防止在放入数的时候，数据溢出，则每个一个数组（桶），大小定为arr.length</span>
		<span class="token comment">//3明显，基数排序是使用空间换时间 </span>
		<span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span> bucket<span class="token operator">=</span><span class="token keyword">new</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token number">10</span><span class="token punctuation">]</span><span class="token punctuation">[</span>arr<span class="token punctuation">.</span>length<span class="token punctuation">]</span><span class="token punctuation">;</span>
		
<span class="token comment">//		为了记录每个桶中，实际存放了多少个数据，我们定义了一个一维数组来记录各个桶中的个数</span>
		<span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> bucketElementCounts<span class="token operator">=</span><span class="token keyword">new</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token number">10</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
		
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>n<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>maxLength<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">,</span>n<span class="token operator">*=</span><span class="token number">10</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
			<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span>arr<span class="token punctuation">.</span>length<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
				<span class="token comment">//取出每个元素的对应位的值进行排序处理，第一次是个位，第二次是十位。。。</span>
				<span class="token keyword">int</span> digitOfElement<span class="token operator">=</span>arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">/</span>n<span class="token operator">%</span><span class="token number">10</span><span class="token punctuation">;</span>
				<span class="token comment">//放入到对应的桶中</span>
				bucket<span class="token punctuation">[</span>digitOfElement<span class="token punctuation">]</span><span class="token punctuation">[</span>bucketElementCounts<span class="token punctuation">[</span>digitOfElement<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">=</span>arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
				bucketElementCounts<span class="token punctuation">[</span>digitOfElement<span class="token punctuation">]</span><span class="token operator">++</span><span class="token punctuation">;</span>
			<span class="token punctuation">&#125;</span>
			
			<span class="token comment">//按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）</span>
			<span class="token keyword">int</span> index<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
			<span class="token comment">//遍历每一桶，并将桶中的数据，放入到原数组</span>
			<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> k<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>k<span class="token operator">&lt;</span>bucketElementCounts<span class="token punctuation">.</span>length<span class="token punctuation">;</span>k<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
				<span class="token comment">//如果桶中，有数据，我们才能放入到原数组</span>
				<span class="token keyword">if</span><span class="token punctuation">(</span>bucketElementCounts<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">!=</span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
					<span class="token comment">//循环该桶即第k个桶，（即第k个一维数组），放入</span>
					<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> l<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>l<span class="token operator">&lt;</span>bucketElementCounts<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">;</span>l<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
						<span class="token comment">//取出元素放入arr</span>
						arr<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token operator">=</span>bucket<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span>l<span class="token punctuation">]</span><span class="token punctuation">;</span>
						index<span class="token operator">++</span><span class="token punctuation">;</span>
					<span class="token punctuation">&#125;</span>
				<span class="token punctuation">&#125;</span>
				<span class="token comment">//第i+1轮处理后，需要将每个bucketElementCounts[k]=0!!!</span>
				bucketElementCounts<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
			<span class="token punctuation">&#125;</span>
		<span class="token punctuation">&#125;</span>		
	<span class="token punctuation">&#125;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>





<h2 id="查找"><a href="#查找" class="headerlink" title="查找"></a>查找</h2><ul>
<li>顺序(线性)查找</li>
<li>二分查找/折半查找</li>
<li>插值查找</li>
<li>斐波那契查找</li>
</ul>
<h3 id="线性查找"><a href="#线性查找" class="headerlink" title="线性查找"></a>线性查找</h3><p>  线性查找不需要被查找的数列有顺序。</p>
<p>  遍历所有的数据，返回一个下标或者多个下标组成的数组。</p>
<h3 id="二分查找"><a href="#二分查找" class="headerlink" title="二分查找"></a>二分查找</h3><p>  二分查找需要在一个有序的数组中使用。</p>
<p>   1、首先确定该数组的中间的下标</p>
<p>​    mid = (left + right) / 2</p>
<p>  2、然后让需要查找的数findVal和arr[mid]比较</p>
<pre><code> 2.1 findVal   arr[mid] ，说明你要查找的数在mid的右边，因此需要递归的向右查找
</code></pre>
<p>​    2.2 findVal &lt; arr[mid] ，说明你要查找的数在mid的左边，因此需要递归的向左查找<br>​    2.3 findVal = arr[mid] ，说明找到，就返回</p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token comment">//通过递归调用直到索引越界或者获得对应值的索引</span>

<span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">int</span> <span class="token function">binarySearch</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token punctuation">,</span> <span class="token keyword">int</span> left<span class="token punctuation">,</span> <span class="token keyword">int</span> right<span class="token punctuation">,</span> <span class="token keyword">int</span> findVal<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>left   right<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>    <span class="token comment">//标志未找到</span>
        <span class="token punctuation">&#125;</span>
        <span class="token keyword">int</span> mid <span class="token operator">=</span> <span class="token punctuation">(</span>left <span class="token operator">+</span> right<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">;</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>arr<span class="token punctuation">[</span>mid<span class="token punctuation">]</span> <span class="token operator">==</span> findVal<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            <span class="token keyword">return</span> mid<span class="token punctuation">;</span>   <span class="token comment">//找到返回当前索引</span>
        <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>arr<span class="token punctuation">[</span>mid<span class="token punctuation">]</span>   findVal<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            <span class="token comment">// 向左边查找</span>
            <span class="token keyword">return</span> <span class="token function">binarySearch</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> left<span class="token punctuation">,</span> mid <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> findVal<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
            <span class="token comment">// 向右边查找</span>
            <span class="token keyword">return</span> <span class="token function">binarySearch</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> right<span class="token punctuation">,</span> findVal<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>



<h3 id="插值查找"><a href="#插值查找" class="headerlink" title="插值查找"></a>插值查找</h3><p>  插值查找算法类似与二分查找，不同的是插值查找，欸此从自适应mid处开始查找。</p>
<p>  对于数据量较大，关键字分布比较均匀的查找表，采用插值查找速度比较快，关键字分布不均匀，插值查找不一定比折半查找效率高。</p>
<p>  将折半查找的mid使用索引公式low表示左边索引left，hight表示右边索引right。key为findVal</p>
<p><img src="./img/%E6%8F%92%E5%80%BC%E6%9F%A5%E6%89%BE.png"></p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java"><span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">int</span> <span class="token function">interpolationSearch</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token punctuation">,</span> <span class="token keyword">int</span> target <span class="token punctuation">,</span> <span class="token keyword">int</span> left <span class="token punctuation">,</span> <span class="token keyword">int</span> right<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>target <span class="token operator">&lt;</span> arr<span class="token punctuation">[</span>left<span class="token punctuation">]</span> <span class="token operator">||</span> target   arr<span class="token punctuation">[</span>right<span class="token punctuation">]</span> <span class="token operator">||</span> left   right<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
			<span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>				
		<span class="token punctuation">&#125;</span>

		<span class="token keyword">int</span> leftToTarget <span class="token operator">=</span> target <span class="token operator">-</span> arr<span class="token punctuation">[</span>left<span class="token punctuation">]</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> rightToLeft <span class="token operator">=</span> arr<span class="token punctuation">[</span>right<span class="token punctuation">]</span> <span class="token operator">-</span> arr<span class="token punctuation">[</span>left<span class="token punctuation">]</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> num <span class="token operator">=</span> right <span class="token operator">-</span> left<span class="token punctuation">;</span>
		<span class="token comment">//中间的值的下标 注意此行与二分查找的区别</span>
		<span class="token keyword">int</span> mid <span class="token operator">=</span> left <span class="token operator">+</span> leftToTarget<span class="token operator">*</span>num<span class="token operator">/</span>rightToLeft<span class="token punctuation">;</span>
		<span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"找了一次，中间值为："</span> <span class="token operator">+</span> mid<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token comment">//目标值小于中间值  取左侧</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>mid<span class="token punctuation">]</span>   target <span class="token operator">&amp;&amp;</span> left <span class="token operator">&lt;=</span> right<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
			<span class="token comment">//递归左侧</span>
			<span class="token keyword">return</span> <span class="token function">interpolationSearch</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span>target <span class="token punctuation">,</span> left <span class="token punctuation">,</span> mid<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">&#125;</span><span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>mid<span class="token punctuation">]</span> <span class="token operator">&lt;</span> target <span class="token operator">&amp;&amp;</span> left <span class="token operator">&lt;=</span> right<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
			<span class="token comment">//目标值大于中间值  取右侧 并且递归</span>
			<span class="token keyword">return</span> <span class="token function">interpolationSearch</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span>target<span class="token punctuation">,</span> mid<span class="token operator">+</span><span class="token number">1</span> <span class="token punctuation">,</span> right<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">&#125;</span><span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
			<span class="token comment">//不大于也不小于 则是相等</span>
			<span class="token keyword">return</span> mid<span class="token punctuation">;</span>
		<span class="token punctuation">&#125;</span>
	<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>





<h3 id="斐波那契-黄金分割法-查找"><a href="#斐波那契-黄金分割法-查找" class="headerlink" title="斐波那契(黄金分割法)查找"></a>斐波那契(黄金分割法)查找</h3><p>  斐波那契查找原理和插值查找和二分查找相同，只是改变了中间节点的位置，为于黄金分割点附近，即mid=low + F(k-1)-1</p>
<p>  数组不够黄金分割时会扩容数组。</p>
<p>  斐波那契需要在有序的数组中使用。</p>
<h2 id="哈希表"><a href="#哈希表" class="headerlink" title="哈希表"></a>哈希表</h2><blockquote>
<p>散列表(哈希表)是根据关键码值而直接进行访问的数据结构，通过关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数，存放记录的数组叫做散列表。</p>
</blockquote>
<p>哈希表的本质上上一个数组（元素是Entry）</p>
<p>这里的 id 是个key，哈希表就是根据key值来通过哈希函数计算得到一个值，这个值就是用来确定这个Entry要存放在哈希表中的位置的，实际上这个值就是一个下标值，来确定放在数组的哪个位置上</p>
<p><img src="./img/%E5%93%88%E5%B8%8C%E8%A1%A8.png"></p>
<h2 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a>二叉树</h2><p>  数组存储方式分析：</p>
<ul>
<li>优点：通过下标方式访问元素，速度块，对于有序数组，可以使用二分查找提高检索速度。</li>
<li>缺点：如果检索具体的某个值，或者插入值会整体移动，效率比较低。</li>
</ul>
<p>  链式存储方式分析</p>
<ul>
<li>优点：在一定程度上对数组存储方式有优化，插入，删除效率高。</li>
<li>缺点：在进行检索时，效率比较低。</li>
</ul>
<p>  树存储方式分析：</p>
<ul>
<li>能提高存储，读取的效率，同时也可以保证数据的插入，删除，修改的速度。</li>
</ul>
<h3 id="遍历方案"><a href="#遍历方案" class="headerlink" title="遍历方案"></a>遍历方案</h3><p><a target="_blank" rel="noopener" href="https://baike.baidu.com/pic/%E4%BA%8C%E5%8F%89%E6%A0%91%E9%81%8D%E5%8E%86/9796049/0/4610b912c8fcc3ce080903ae9245d688d53f2066?fr=lemma&ct=single"><img src="https://bkimg.cdn.bcebos.com/pic/4610b912c8fcc3ce080903ae9245d688d53f2066?x-bce-process=image/resize,m_lfit,w_440,limit_1/format,f_auto" alt="二叉树的前序遍历"></a>二叉树的前序遍历</p>
<p>递归</p>
<p>根结点</p>
<p>⑴访问结点本身（N），</p>
<p>⑵遍历该结点的左子树（L），</p>
<p>⑶遍历该结点的右子树（R）。</p>
<p>以上三种操作有六种执行次序：</p>
<p>NLR、LNR、LRN、NRL、RNL、RLN。</p>
<p>注意：</p>
<p>前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。</p>
<h3 id="遍历命名"><a href="#遍历命名" class="headerlink" title="遍历命名"></a>遍历命名</h3><p>根据访问结点操作发生位置命名：</p>
<p>① NLR：<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E5%89%8D%E5%BA%8F%E9%81%8D%E5%8E%86">前序遍历</a>(Preorder Traversal 亦称（先序遍历））</p>
<p>——访问根结点的操作发生在遍历其左右子树之前。</p>
<p>② LNR：<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86">中序遍历</a>(Inorder Traversal)</p>
<p>——访问根结点的操作发生在遍历其左右子树之中（间）。</p>
<p>③ LRN：<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86">后序遍历</a>(Postorder Traversal)</p>
<p>——访问根结点的操作发生在遍历其左右子树之后。</p>
<h3 id="顺序存储二叉树"><a href="#顺序存储二叉树" class="headerlink" title="顺序存储二叉树"></a>顺序存储二叉树</h3><p>  从数据存储来看，数组存储方式和树的存储方式可以互相转换，即数组可以转换成树，树也可以转换成数组。</p>
<p>  顺序存储二叉树的特点：</p>
<ul>
<li>顺序二叉树通常只考虑完全二叉树</li>
<li>顺序二叉树编号从0开始</li>
<li>第n个元素的左子节点为 2*n+1</li>
<li>第n个元素的右子节点为2*n+2</li>
<li>第n个元素的父节点为(n-1)/2</li>
</ul>
<p><img src="./img/%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E4%BA%8C%E5%8F%89%E6%A0%91.png"></p>
<pre class="line-numbers language-java" data-language="java"><code class="language-java">
<span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">ArrayBinaryTree</span> <span class="token punctuation">&#123;</span>
   <span class="token keyword">private</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> array<span class="token punctuation">;</span><span class="token comment">//存储数据节点的数组</span>
   <span class="token keyword">public</span> <span class="token class-name">ArrayBinaryTree</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> array<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
     <span class="token keyword">this</span><span class="token punctuation">.</span>array <span class="token operator">=</span> array<span class="token punctuation">;</span>
   <span class="token punctuation">&#125;</span>
   
   <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">preOrder</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
     <span class="token function">preOrder</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
   <span class="token punctuation">&#125;</span>
   
   <span class="token comment">//数组的输出顺序转换成对应的二叉树的前序遍历</span>
   <span class="token keyword">private</span> <span class="token keyword">void</span> <span class="token function">preOrder</span><span class="token punctuation">(</span><span class="token keyword">int</span> index<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
     <span class="token keyword">if</span> <span class="token punctuation">(</span>array <span class="token operator">==</span> <span class="token keyword">null</span> <span class="token operator">||</span> array<span class="token punctuation">.</span>length <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
       <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"数组为空，不能进行二叉树的前序遍历"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
       <span class="token keyword">return</span><span class="token punctuation">;</span>
     <span class="token punctuation">&#125;</span>
     
     <span class="token comment">//输出当前这个元素</span>
     <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>array<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
     
     <span class="token comment">//向左递归遍历</span>
     <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">*</span> <span class="token number">2</span> <span class="token operator">+</span> <span class="token number">1</span> <span class="token operator">&lt;</span> array<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
       <span class="token function">preOrder</span><span class="token punctuation">(</span>index <span class="token operator">*</span> <span class="token number">2</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
     <span class="token punctuation">&#125;</span>
     
     <span class="token comment">//向右递归遍历</span>
     <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">*</span> <span class="token number">2</span> <span class="token operator">+</span> <span class="token number">2</span> <span class="token operator">&lt;</span> array<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
       <span class="token function">preOrder</span><span class="token punctuation">(</span>index <span class="token operator">*</span> <span class="token number">2</span> <span class="token operator">+</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
     <span class="token punctuation">&#125;</span>
   <span class="token punctuation">&#125;</span>
   
   <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">middleOrder</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
     <span class="token function">middleOrder</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
   <span class="token punctuation">&#125;</span>
   
   <span class="token comment">//数组的输出顺序转换成对应的二叉树的中序遍历</span>
   <span class="token keyword">private</span> <span class="token keyword">void</span> <span class="token function">middleOrder</span><span class="token punctuation">(</span><span class="token keyword">int</span> index<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
     <span class="token keyword">if</span> <span class="token punctuation">(</span>array <span class="token operator">==</span> <span class="token keyword">null</span> <span class="token operator">||</span> array<span class="token punctuation">.</span>length <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
       <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"数组为空，不能进行二叉树的前序遍历"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
       <span class="token keyword">return</span><span class="token punctuation">;</span>
     <span class="token punctuation">&#125;</span>
     
     <span class="token comment">//向左递归遍历</span>
     <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">*</span> <span class="token number">2</span> <span class="token operator">+</span> <span class="token number">1</span> <span class="token operator">&lt;</span> array<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
       <span class="token function">middleOrder</span><span class="token punctuation">(</span>index <span class="token operator">*</span> <span class="token number">2</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
     <span class="token punctuation">&#125;</span>
     
     <span class="token comment">//输出当前这个元素</span>
     <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>array<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
     
     <span class="token comment">//向右递归遍历</span>
     <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">*</span> <span class="token number">2</span> <span class="token operator">+</span> <span class="token number">2</span> <span class="token operator">&lt;</span> array<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
       <span class="token function">middleOrder</span><span class="token punctuation">(</span>index <span class="token operator">*</span> <span class="token number">2</span> <span class="token operator">+</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
     <span class="token punctuation">&#125;</span>
   <span class="token punctuation">&#125;</span>
   
   <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">postOrder</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
     <span class="token function">postOrder</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
   <span class="token punctuation">&#125;</span>
   
   <span class="token comment">//数组的输出顺序转换成对应的二叉树的后序遍历</span>
   <span class="token keyword">private</span> <span class="token keyword">void</span> <span class="token function">postOrder</span><span class="token punctuation">(</span><span class="token keyword">int</span> index<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
     <span class="token keyword">if</span> <span class="token punctuation">(</span>array <span class="token operator">==</span> <span class="token keyword">null</span> <span class="token operator">||</span> array<span class="token punctuation">.</span>length <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
       <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"数组为空，不能进行二叉树的前序遍历"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
       <span class="token keyword">return</span><span class="token punctuation">;</span>
     <span class="token punctuation">&#125;</span>
     
     <span class="token comment">//向左递归遍历</span>
     <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">*</span> <span class="token number">2</span> <span class="token operator">+</span> <span class="token number">1</span> <span class="token operator">&lt;</span> array<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
       <span class="token function">postOrder</span><span class="token punctuation">(</span>index <span class="token operator">*</span> <span class="token number">2</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
     <span class="token punctuation">&#125;</span>
     
     <span class="token comment">//向右递归遍历</span>
     <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">*</span> <span class="token number">2</span> <span class="token operator">+</span> <span class="token number">2</span> <span class="token operator">&lt;</span> array<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
       <span class="token function">postOrder</span><span class="token punctuation">(</span>index <span class="token operator">*</span> <span class="token number">2</span> <span class="token operator">+</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
     <span class="token punctuation">&#125;</span>
     
     <span class="token comment">//输出当前这个元素</span>
     <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>array<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
   <span class="token punctuation">&#125;</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>





<h3 id="线索化二叉树"><a href="#线索化二叉树" class="headerlink" title="线索化二叉树"></a>线索化二叉树</h3><blockquote>
<p> n个几点的二叉链表中含有n + 1个空指针域，利用二叉链表中空的指针域，存放指向该节点在某种遍历次序下的前驱或者后继节点的指针(这种附加的指针称为线索)</p>
</blockquote>
<blockquote>
<p>s这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树，根据线索性质的不同，线索二叉树可以分为前序线索二叉树，中序线索二叉树，后序线索二叉树</p>
</blockquote>

                
            </div>
            <hr/>

            

    <div class="reprint" id="reprint-statement">
        
            <div class="reprint__author">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-user">
                        Author:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="/about" rel="external nofollow noreferrer">凡诚</a>
                </span>
            </div>
            <div class="reprint__type">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-link">
                        Link:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="http://example.com/2021/11/08/java-shu-ju-jie-gou/">http://example.com/2021/11/08/java-shu-ju-jie-gou/</a>
                </span>
            </div>
            <div class="reprint__notice">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-copyright">
                        Reprint policy:
                    </i>
                </span>
                <span class="reprint-info">
                    All articles in this blog are used except for special statements
                    <a href="https://creativecommons.org/licenses/by/4.0/deed.zh" rel="external nofollow noreferrer" target="_blank">CC BY 4.0</a>
                    reprint polocy. If reproduced, please indicate source
                    <a href="/about" target="_blank">凡诚</a>
                    !
                </span>
            </div>
        
    </div>

    <script async defer>
      document.addEventListener("copy", function (e) {
        let toastHTML = '<span>Copied successfully, please follow the reprint policy of this article</span><button class="btn-flat toast-action" onclick="navToReprintStatement()" style="font-size: smaller">more</a>';
        M.toast({html: toastHTML})
      });

      function navToReprintStatement() {
        $("html, body").animate({scrollTop: $("#reprint-statement").offset().top - 80}, 800);
      }
    </script>



            <div class="tag_share" style="display: block;">
                <div class="post-meta__tag-list" style="display: inline-block;">
                    
                        <div class="article-tag">
                            
                                <a href="/tags/java/">
                                    <span class="chip bg-color">java</span>
                                </a>
                            
                                <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">
                                    <span class="chip bg-color">数据结构</span>
                                </a>
                            
                        </div>
                    
                </div>
                <div class="post_share" style="zoom: 80%; width: fit-content; display: inline-block; float: right; margin: -0.15rem 0;">
                    <link rel="stylesheet" type="text/css" href="/libs/share/css/share.min.css">
<div id="article-share">

    
    <div class="social-share" data-sites="twitter,facebook,google,qq,qzone,wechat,weibo,douban,linkedin" data-wechat-qrcode-helper="<p>微信扫一扫即可分享！</p>"></div>
    <script src="/libs/share/js/social-share.min.js"></script>
    

    

</div>

                </div>
            </div>
            
                <style>
    #reward {
        margin: 40px 0;
        text-align: center;
    }

    #reward .reward-link {
        font-size: 1.4rem;
        line-height: 38px;
    }

    #reward .btn-floating:hover {
        box-shadow: 0 6px 12px rgba(0, 0, 0, 0.2), 0 5px 15px rgba(0, 0, 0, 0.2);
    }

    #rewardModal {
        width: 320px;
        height: 350px;
    }

    #rewardModal .reward-title {
        margin: 15px auto;
        padding-bottom: 5px;
    }

    #rewardModal .modal-content {
        padding: 10px;
    }

    #rewardModal .close {
        position: absolute;
        right: 15px;
        top: 15px;
        color: rgba(0, 0, 0, 0.5);
        font-size: 1.3rem;
        line-height: 20px;
        cursor: pointer;
    }

    #rewardModal .close:hover {
        color: #ef5350;
        transform: scale(1.3);
        -moz-transform:scale(1.3);
        -webkit-transform:scale(1.3);
        -o-transform:scale(1.3);
    }

    #rewardModal .reward-tabs {
        margin: 0 auto;
        width: 210px;
    }

    .reward-tabs .tabs {
        height: 38px;
        margin: 10px auto;
        padding-left: 0;
    }

    .reward-content ul {
        padding-left: 0 !important;
    }

    .reward-tabs .tabs .tab {
        height: 38px;
        line-height: 38px;
    }

    .reward-tabs .tab a {
        color: #fff;
        background-color: #ccc;
    }

    .reward-tabs .tab a:hover {
        background-color: #ccc;
        color: #fff;
    }

    .reward-tabs .wechat-tab .active {
        color: #fff !important;
        background-color: #22AB38 !important;
    }

    .reward-tabs .alipay-tab .active {
        color: #fff !important;
        background-color: #019FE8 !important;
    }

    .reward-tabs .reward-img {
        width: 210px;
        height: 210px;
    }
</style>

<div id="reward">
    <a href="#rewardModal" class="reward-link modal-trigger btn-floating btn-medium waves-effect waves-light red">赏</a>

    <!-- Modal Structure -->
    <div id="rewardModal" class="modal">
        <div class="modal-content">
            <a class="close modal-close"><i class="fas fa-times"></i></a>
            <h4 class="reward-title">你的赏识是我前进的动力</h4>
            <div class="reward-content">
                <div class="reward-tabs">
                    <ul class="tabs row">
                        <li class="tab col s6 alipay-tab waves-effect waves-light"><a href="#alipay">支付宝</a></li>
                        <li class="tab col s6 wechat-tab waves-effect waves-light"><a href="#wechat">微 信</a></li>
                    </ul>
                    <div id="alipay">
                        <img src="/medias/reward/alipay.jpg" class="reward-img" alt="支付宝打赏二维码">
                    </div>
                    <div id="wechat">
                        <img src="/medias/reward/wechat.png" class="reward-img" alt="微信打赏二维码">
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>

<script>
    $(function () {
        $('.tabs').tabs();
    });
</script>

            
        </div>
    </div>

    

    

    

    
    <div class="livere-card card" data-aos="fade-up">
    <!-- 来必力City版安装代码 -->
    <div id="lv-container" class="card-content" data-id="city" data-uid="MTAyMC81NzU4NC8zNDA0OA==">
        <script type="text/javascript">
            (function (d, s) {
                let j, e = d.getElementsByTagName(s)[0];
                if (typeof LivereTower === 'function') {
                    return;
                }

                j = d.createElement(s);
                j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
                j.async = true;

                e.parentNode.insertBefore(j, e);
            })(document, 'script');
        </script>
        <noscript>为正常使用来必力评论功能请激活JavaScript。</noscript>
    </div>
    <!-- City版安装代码已完成 -->
</div>
    

    

    

    

    

<article id="prenext-posts" class="prev-next articles">
    <div class="row article-row">
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge left-badge text-color">
                <i class="fas fa-chevron-left"></i>&nbsp;Previous</div>
            <div class="card">
                <a href="/2021/11/08/web-ji-chu/">
                    <div class="card-image">
                        
                        
                        <img src="/medias/featureimages/3.jpg" class="responsive-img" alt="html基础">
                        
                        <span class="card-title">html基础</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            Markdown 是一种轻量级标记语言，它允许人们使用易读易写的纯文本格式编写文档。
                        
                    </div>
                    <div class="publish-info">
                        <span class="publish-date">
                            <i class="far fa-clock fa-fw icon-date"></i>2021-11-08
                        </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/%E5%89%8D%E7%AB%AF%E6%8A%80%E6%9C%AF/" class="post-category">
                                    前端技术
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/html/">
                        <span class="chip bg-color">html</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge right-badge text-color">
                Next&nbsp;<i class="fas fa-chevron-right"></i>
            </div>
            <div class="card">
                <a href="/2021/11/08/jquery/">
                    <div class="card-image">
                        
                        
                        <img src="/medias/featureimages/6.jpg" class="responsive-img" alt="jQuery基础">
                        
                        <span class="card-title">jQuery基础</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            Markdown jQuery是一个快速、简洁的JavaScript框架，是继Prototype之后又一个优秀的JavaScript代码库。
                        
                    </div>
                    <div class="publish-info">
                            <span class="publish-date">
                                <i class="far fa-clock fa-fw icon-date"></i>2021-11-08
                            </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/%E5%89%8D%E7%AB%AF%E6%8A%80%E6%9C%AF/" class="post-category">
                                    前端技术
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/html/">
                        <span class="chip bg-color">html</span>
                    </a>
                    
                    <a href="/tags/javaScript/">
                        <span class="chip bg-color">javaScript</span>
                    </a>
                    
                    <a href="/tags/jQuery/">
                        <span class="chip bg-color">jQuery</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
    </div>
</article>

</div>



<!-- 代码块功能依赖 -->
<script type="text/javascript" src="/libs/codeBlock/codeBlockFuction.js"></script>

<!-- 代码语言 -->

<script type="text/javascript" src="/libs/codeBlock/codeLang.js"></script>


<!-- 代码块复制 -->

<script type="text/javascript" src="/libs/codeBlock/codeCopy.js"></script>


<!-- 代码块收缩 -->

<script type="text/javascript" src="/libs/codeBlock/codeShrink.js"></script>


    </div>
    <div id="toc-aside" class="expanded col l3 hide-on-med-and-down">
        <div class="toc-widget card" style="background-color: white;">
            <div class="toc-title"><i class="far fa-list-alt"></i>&nbsp;&nbsp;TOC</div>
            <div id="toc-content"></div>
        </div>
    </div>
</div>

<!-- TOC 悬浮按钮. -->

<div id="floating-toc-btn" class="hide-on-med-and-down">
    <a class="btn-floating btn-large bg-color">
        <i class="fas fa-list-ul"></i>
    </a>
</div>


<script src="/libs/tocbot/tocbot.min.js"></script>
<script>
    $(function () {
        tocbot.init({
            tocSelector: '#toc-content',
            contentSelector: '#articleContent',
            headingsOffset: -($(window).height() * 0.4 - 45),
            collapseDepth: Number('0'),
            headingSelector: 'h2, h3, h4'
        });

        // modify the toc link href to support Chinese.
        let i = 0;
        let tocHeading = 'toc-heading-';
        $('#toc-content a').each(function () {
            $(this).attr('href', '#' + tocHeading + (++i));
        });

        // modify the heading title id to support Chinese.
        i = 0;
        $('#articleContent').children('h2, h3, h4').each(function () {
            $(this).attr('id', tocHeading + (++i));
        });

        // Set scroll toc fixed.
        let tocHeight = parseInt($(window).height() * 0.4 - 64);
        let $tocWidget = $('.toc-widget');
        $(window).scroll(function () {
            let scroll = $(window).scrollTop();
            /* add post toc fixed. */
            if (scroll > tocHeight) {
                $tocWidget.addClass('toc-fixed');
            } else {
                $tocWidget.removeClass('toc-fixed');
            }
        });

        
        /* 修复文章卡片 div 的宽度. */
        let fixPostCardWidth = function (srcId, targetId) {
            let srcDiv = $('#' + srcId);
            if (srcDiv.length === 0) {
                return;
            }

            let w = srcDiv.width();
            if (w >= 450) {
                w = w + 21;
            } else if (w >= 350 && w < 450) {
                w = w + 18;
            } else if (w >= 300 && w < 350) {
                w = w + 16;
            } else {
                w = w + 14;
            }
            $('#' + targetId).width(w);
        };

        // 切换TOC目录展开收缩的相关操作.
        const expandedClass = 'expanded';
        let $tocAside = $('#toc-aside');
        let $mainContent = $('#main-content');
        $('#floating-toc-btn .btn-floating').click(function () {
            if ($tocAside.hasClass(expandedClass)) {
                $tocAside.removeClass(expandedClass).hide();
                $mainContent.removeClass('l9');
            } else {
                $tocAside.addClass(expandedClass).show();
                $mainContent.addClass('l9');
            }
            fixPostCardWidth('artDetail', 'prenext-posts');
        });
        
    });
</script>

    

</main>




    <footer class="page-footer bg-color">
    
        <link rel="stylesheet" href="/libs/aplayer/APlayer.min.css">
<style>
    .aplayer .aplayer-lrc p {
        
        font-size: 12px;
        font-weight: 700;
        line-height: 16px !important;
    }

    .aplayer .aplayer-lrc p.aplayer-lrc-current {
        
        font-size: 15px;
        color: blue;
    }

    
    .aplayer.aplayer-fixed.aplayer-narrow .aplayer-body {
        left: -66px !important;
    }

    .aplayer.aplayer-fixed.aplayer-narrow .aplayer-body:hover {
        left: 0px !important;
    }

    
</style>
<div class="">
    
    <div class="row">
        <meting-js class="col l8 offset-l2 m10 offset-m1 s12"
                   server="netease"
                   type="playlist"
                   id="2477330090"
                   fixed='true'
                   autoplay='false'
                   theme='blue'
                   loop='all'
                   order='random'
                   preload='auto'
                   volume='0.7'
                   list-folded='true'
        >
        </meting-js>
    </div>
</div>

<script src="/libs/aplayer/APlayer.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/meting@2/dist/Meting.min.js"></script>

    
    <div class="container row center-align" style="margin-bottom: 15px !important;">
        <div class="col s12 m8 l8 copy-right">
            Copyright&nbsp;&copy;
            
                <span id="year">2022</span>
            
            <span id="year">2022</span>
            <a href="/about" target="_blank">凡诚</a>
            &nbsp;&nbsp;<a href="https://hexo.io/" target="_blank"></a>
            |&nbsp;Theme&nbsp;<a href="https://github.com/blinkfox/hexo-theme-matery" target="_blank">Matery</a>
            <br>
            
            &nbsp;<i class="fas fa-chart-area"></i>&nbsp;站点总字数:&nbsp;<span
                class="white-color">607.1k</span>&nbsp;字
            
            
            
            
            
            
            <span id="busuanzi_container_site_pv">
                |&nbsp;<i class="far fa-eye"></i>&nbsp;总访问量:&nbsp;<span id="busuanzi_value_site_pv"
                    class="white-color"></span>&nbsp;次
            </span>
            
            
            <span id="busuanzi_container_site_uv">
                |&nbsp;<i class="fas fa-users"></i>&nbsp;总访问人数:&nbsp;<span id="busuanzi_value_site_uv"
                    class="white-color"></span>&nbsp;人
            </span>
            
            <br>
            
            <span id="sitetime">载入运行时间...</span>
            <script>
                function siteTime() {
                    var seconds = 1000;
                    var minutes = seconds * 60;
                    var hours = minutes * 60;
                    var days = hours * 24;
                    var years = days * 365;
                    var today = new Date();
                    var startYear = "2022";
                    var startMonth = "11";
                    var startDate = "7";
                    var startHour = "0";
                    var startMinute = "0";
                    var startSecond = "0";
                    var todayYear = today.getFullYear();
                    var todayMonth = today.getMonth() + 1;
                    var todayDate = today.getDate();
                    var todayHour = today.getHours();
                    var todayMinute = today.getMinutes();
                    var todaySecond = today.getSeconds();
                    var t1 = Date.UTC(startYear, startMonth, startDate, startHour, startMinute, startSecond);
                    var t2 = Date.UTC(todayYear, todayMonth, todayDate, todayHour, todayMinute, todaySecond);
                    var diff = t2 - t1;
                    var diffYears = Math.floor(diff / years);
                    var diffDays = Math.floor((diff / days) - diffYears * 365);
                    var diffHours = Math.floor((diff - (diffYears * 365 + diffDays) * days) / hours);
                    var diffMinutes = Math.floor((diff - (diffYears * 365 + diffDays) * days - diffHours * hours) /
                        minutes);
                    var diffSeconds = Math.floor((diff - (diffYears * 365 + diffDays) * days - diffHours * hours -
                        diffMinutes * minutes) / seconds);
                    if (startYear == todayYear) {
                        document.getElementById("year").innerHTML = todayYear;
                        document.getElementById("sitetime").innerHTML = "本站已安全运行 " + diffDays + " 天 " + diffHours +
                            " 小时 " + diffMinutes + " 分钟 " + diffSeconds + " 秒";
                    } else {
                        document.getElementById("year").innerHTML = startYear + " - " + todayYear;
                        document.getElementById("sitetime").innerHTML = "本站已安全运行 " + diffYears + " 年 " + diffDays +
                            " 天 " + diffHours + " 小时 " + diffMinutes + " 分钟 " + diffSeconds + " 秒";
                    }
                }
                setInterval(siteTime, 1000);
            </script>
            
            <br>
            
        </div>
        <div class="col s12 m4 l4 social-link social-statis">
    <a href="https://github.com/fanshicheng" class="tooltipped" target="_blank" data-tooltip="访问我的GitHub" data-position="top" data-delay="50">
        <i class="fab fa-github"></i>
    </a>



    <a href="mailto:2639144944@qq.com" class="tooltipped" target="_blank" data-tooltip="邮件联系我" data-position="top" data-delay="50">
        <i class="fas fa-envelope-open"></i>
    </a>







    <a href="tencent://AddContact/?fromId=50&fromSubId=1&subcmd=all&uin=2639144944" class="tooltipped" target="_blank" data-tooltip="QQ联系我: 2639144944" data-position="top" data-delay="50">
        <i class="fab fa-qq"></i>
    </a>







</div>
    </div>
</footer>

<div class="progress-bar"></div>


    <!-- 搜索遮罩框 -->
<div id="searchModal" class="modal">
    <div class="modal-content">
        <div class="search-header">
            <span class="title"><i class="fas fa-search"></i>&nbsp;&nbsp;Search</span>
            <input type="search" id="searchInput" name="s" placeholder="Please enter a search keyword"
                   class="search-input">
        </div>
        <div id="searchResult"></div>
    </div>
</div>

<script type="text/javascript">
$(function () {
    var searchFunc = function (path, search_id, content_id) {
        'use strict';
        $.ajax({
            url: path,
            dataType: "xml",
            success: function (xmlResponse) {
                // get the contents from search data
                var datas = $("entry", xmlResponse).map(function () {
                    return {
                        title: $("title", this).text(),
                        content: $("content", this).text(),
                        url: $("url", this).text()
                    };
                }).get();
                var $input = document.getElementById(search_id);
                var $resultContent = document.getElementById(content_id);
                $input.addEventListener('input', function () {
                    var str = '<ul class=\"search-result-list\">';
                    var keywords = this.value.trim().toLowerCase().split(/[\s\-]+/);
                    $resultContent.innerHTML = "";
                    if (this.value.trim().length <= 0) {
                        return;
                    }
                    // perform local searching
                    datas.forEach(function (data) {
                        var isMatch = true;
                        var data_title = data.title.trim().toLowerCase();
                        var data_content = data.content.trim().replace(/<[^>]+>/g, "").toLowerCase();
                        var data_url = data.url;
                        data_url = data_url.indexOf('/') === 0 ? data.url : '/' + data_url;
                        var index_title = -1;
                        var index_content = -1;
                        var first_occur = -1;
                        // only match artiles with not empty titles and contents
                        if (data_title !== '' && data_content !== '') {
                            keywords.forEach(function (keyword, i) {
                                index_title = data_title.indexOf(keyword);
                                index_content = data_content.indexOf(keyword);
                                if (index_title < 0 && index_content < 0) {
                                    isMatch = false;
                                } else {
                                    if (index_content < 0) {
                                        index_content = 0;
                                    }
                                    if (i === 0) {
                                        first_occur = index_content;
                                    }
                                }
                            });
                        }
                        // show search results
                        if (isMatch) {
                            str += "<li><a href='" + data_url + "' class='search-result-title'>" + data_title + "</a>";
                            var content = data.content.trim().replace(/<[^>]+>/g, "");
                            if (first_occur >= 0) {
                                // cut out 100 characters
                                var start = first_occur - 20;
                                var end = first_occur + 80;
                                if (start < 0) {
                                    start = 0;
                                }
                                if (start === 0) {
                                    end = 100;
                                }
                                if (end > content.length) {
                                    end = content.length;
                                }
                                var match_content = content.substr(start, end);
                                // highlight all keywords
                                keywords.forEach(function (keyword) {
                                    var regS = new RegExp(keyword, "gi");
                                    match_content = match_content.replace(regS, "<em class=\"search-keyword\">" + keyword + "</em>");
                                });

                                str += "<p class=\"search-result\">" + match_content + "...</p>"
                            }
                            str += "</li>";
                        }
                    });
                    str += "</ul>";
                    $resultContent.innerHTML = str;
                });
            }
        });
    };

    searchFunc('/search.xml', 'searchInput', 'searchResult');
});
</script>

    <!-- 回到顶部按钮 -->
<div id="backTop" class="top-scroll">
    <a class="btn-floating btn-large waves-effect waves-light" href="#!">
        <i class="fas fa-arrow-up"></i>
    </a>
</div>

    <script type="text/javascript">
        var OriginTitile=document.title,st;
        document.addEventListener("visibilitychange",function(){
            document.hidden?(document.title="(Ő∀Ő3)ノ",clearTimeout(st)):(document.title="ヽ(●-`Д´-)ノ欢迎回来",st=setTimeout(function(){document.title=OriginTitile},3e3))
        })
    </script>
    <!-- <script src="/js/cursor.js"></script> -->
    <script type="text/javascript">
        //只在桌面版网页启用特效
        var windowWidth = $(window).width();
        if (windowWidth > 768) {
            document.write('<script type="text/javascript" src="/js/sakura.js"><\/script>');
        }
        </script>
    <script src="/libs/materialize/materialize.min.js"></script>
    <script src="/libs/masonry/masonry.pkgd.min.js"></script>
    <script src="/libs/aos/aos.js"></script>
    <script src="/libs/scrollprogress/scrollProgress.min.js"></script>
    <script src="/libs/lightGallery/js/lightgallery-all.min.js"></script>
    <script src="/js/matery.js"></script>

    <!-- Baidu Analytics -->

    <!-- Baidu Push -->

<script>
    (function () {
        var bp = document.createElement('script');
        var curProtocol = window.location.protocol.split(':')[0];
        if (curProtocol === 'https') {
            bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
        } else {
            bp.src = 'http://push.zhanzhang.baidu.com/push.js';
        }
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(bp, s);
    })();
</script>

    
    
    <script async src="/libs/others/busuanzi.pure.mini.js"></script>
    

    

    
    <script>
        (function (i, s, o, g, r, a, m) {
            i["DaoVoiceObject"] = r;
            i[r] = i[r] || function () {
                (i[r].q = i[r].q || []).push(arguments)
            }, i[r].l = 1 * new Date();
            a = s.createElement(o), m = s.getElementsByTagName(o)[0];
            a.async = 1;
            a.src = g;
            a.charset = "utf-8";
            m.parentNode.insertBefore(a, m)
        })(window, document, "script", ('https:' == document.location.protocol ? 'https:' : 'http:') +
            "//widget.daovoice.io/widget/6984b559.js", "daovoice")
        daovoice('init', {
            app_id: "377cb7de"
        });
        daovoice('update');
    </script>
    

	
    
    <script type="text/javascript" color="0,0,255"
        pointColor="0,0,255" opacity='0.7'
        zIndex="-1" count="99"
        src="/libs/background/canvas-nest.js"></script>
    

    

    

    
    <script src="/libs/instantpage/instantpage.js" type="module"></script>
    
    <!-- 冒泡 -->
    
<canvas class="fireworks" style="position: fixed;left: 0;top: 0;z-index: 1; pointer-events: none;" ></canvas> 
<script type="text/javascript" src="//cdn.bootcss.com/animejs/2.2.0/anime.min.js"></script> 
<script type="text/javascript" src="/js/fireworks.js"></script>


</body>

</html>
